Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let n≥ 3, let k be an integer, and let G be a graph of order n with minimum degree δ(G)≥(1-1/2^k)n. A k-edge colouring is a decomposition E(G)=bigcup_i=1^kE(G_i), where each G_i is a spanning colour class. Scott–White's multicolour…
Let G be a weakly perfect graph, meaning that its clique number and chromatic number agree, ω(G)=χ(G). A vertex v∈ V(G) is contained in a maximum clique of G if it belongs to a clique of size ω(G). Vertex-maximum-clique criterion. Any…
For each integer n≥ 3, let vec K_n denote the complete directed graph on n vertices, and let genfrac 0pt1vec K_nn-2 denote the number of admissible partitions into n-2 blocks arising from the transitivity functor for vec K_n. Transitivity…
(41) Lionel Levine: "If you have a graph with a harmonic action, then its critical group comes with some extra structure, namely a group of automorphisms of the graph. That extra object might be worth studying."
Let G be a cycle of length 2ℓ whose edges are colored with h colors. Let M_0 and M_1 be the perfect matchings consisting of the even and odd edges, respectively, and let p_M∈ Z_+^h record the number of edges of each color in a matching M.…
Let G be a graph, let lrw(G) denote its linear rank-width, and let lsfw(G) denote its sequential cable width. Affine upper-bound conjecture. For every graph G, lsfw(G)≤ 2 lrw(G)+2. The preceding results establish the corresponding lower…
A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. A cubic graph is essentially 4-edge-connected if it has no non-trivial 3-edge-cuts. Let G be an essentially 4-edge-connected pseudo…
Let M be a matroid of rank r, and for 0 ≤ i ≤ r let w_i be the number of closed sets of rank i. Conjecture w_0,w_1,…,w_r is unimodal. Conjecture w_0,w_1,…,w_r is log-concave.
Caccetta–Häggkvist special-case conjecture: If G is a digraph with n vertices and no directed cycle of length at most 3, then some vertex of G has outdegree less than n/3.
Let τ be a triangular partition of size n, and let A_τ(q,t) be the associated polynomial. For each partition λ of length at most 2, write s_λ(q,t) for the corresponding Schur polynomial, and restrict to |λ|≤ |τ|. Positive Schur-expansion…
Let G be a bridgeless graph, and let γ(G)=γ be its domination number, where a dominating set is a vertex set D such that every vertex in V(G)∖ D is adjacent to at least one vertex of D. Write overrightarrowdiam(G) for the oriented diameter…
An almost m-ary NPS is a nearly perfect sequence over an alphabet with m-th roots of unity, allowing two zero-symbols; its type is the pair (γ_1,γ_2), and its period is n+2. The two zero-symbols are consecutive when they occur at adjacent…
Let R be an arbitrary ring with Jacobson radical J, and suppose that R/J=M_n_1(F_1) × … × M_n_k(F_k), where each F_i is a finite field and n_i≥ 2 for all i. For a finite ring A, let τ(A) denote its total graph and let γ(τ(A)) denote the…
What is the possible structure of extremal graphs; in particular, does every extremal graph problem formulated by optimizing subgraph densities subject to fixed densities have an extremal family with a finitely forcible graphon limit, and…
Given a prime p and b, can one decide in deterministic polynomial time whether b generates (Z/pZ)^*?
What are the multigraded Betti numbers β_i,m of L_n^(s)∩ Z^n?
For every finite simple connected graph G=(V,E), let N_G(v) denote the neighborhood of v, let α(G[N_G(v)]) be the independence number of the subgraph induced by N_G(v), and define the average local independence by AvgInd(G)=1/|V|∑_v∈…
Conjecture For every k, there exists an integer f(k) such that if D is a digraph whose arcs are colored with k colors, then D has a S set which is the union of f(k) stables sets so that every vertex has a monochromatic path to some vertex…
Let G and H be graphs, let GmathbinsquareH denote their Cartesian product, and let gp^-(G) denote the lower general position number of G. Kruft's conjecture. For any graphs G and H, gp^-(GmathbinsquareH)≥mingp^-(G),gp^-(H). The inequality…
Let G be a graph with maximum degree Δ. For a positive integer k, let ι_k(G) denote the minimum size of a vertex set whose closed neighborhood leaves no induced copy of K_k, and let ir(G) denote the irredundance number. Let c_Δ(k) be the…