Colourings, decompositions and extremal graphs: many graph-theory problems ask for an explicit object that a program can check, which makes progress by AI search and verification especially clear.
Find the largest graphs with maximum degree d and diameter k. Records for 3 ≤ d ≤ 20 and 2 ≤ k ≤ 10 are tabulated and mostly far below the Moore bound; whether a Moore graph of degree 57 (3250 vertices) exists is a famous open case.
Narrow the gap 36 ≤ R(4,6) ≤ 40. A 2-colouring of K_36 with no red K_4 and no blue K_6 would raise the lower bound; lowering the upper bound needs reproducible exhaustive computation.
Narrow the gap between the known lower and upper bounds for R(5,5), currently 43 ≤ R(5,5) ≤ 46.
Prove Hill's conjecture cr(K_n) = ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ and Zarankiewicz's conjecture for K_{m,n}. Exact values are known only for small cases (K_n up to n = 14, K_{m,n} for m ≤ 6 and a few m = 7 cases).
Every tree with n vertices has a graceful labelling, i.e. vertex labels 0..n−1 whose edge differences are exactly 1..n−1. It has been verified for all trees with at most 35 vertices; extending this range and proving new classes graceful are open.
Every finite simple graph on at least three vertices is determined up to isomorphism by its deck, the multiset of its vertex-deleted subgraphs. Verified by computer for all graphs up to 13 vertices; open in general.
In topological graph theory, a thrackle is a drawing of a finite graph in the plane in which every pair of edges meets precisely once, either at a common endpoint or at a proper crossing.
Let G be a finite graph with minimum degree at least 3. Must G contain a cycle of length 2^k for some k ≥ 2?
C_27b is the highest possible chromatic number for any biplanar graph.
For 0 ≤ ρ ≤ 1, let C(ρ) denote the largest quantity such that any graph on n vertices and (ρ+o(1)) C(n, 2) edges will have at least (C(ρ)-o(1)) C(n, 3) triangles. What is C(ρ)?
Let C_7 denote the cycle graph on 7 vertices. We define C_9 to be the Shannon capacity of mathcal C_7: C_9 := Θ(mathcal C_7), where for a graph G, the Shannon capacity Θ(G) is defined by Θ(G) := sup_n ≥ 1 α(G^boxtimes n)^1/n.
A graphon is a symmetric measurable function W : [0,1]^2 → [0,1]. Given a graphon W and a finite graph H = (V(H),E(H)), the homomorphism density t(H,W) is defined as t(H,W) = ∫_[0,1]^V(H) Π_v,w ∈ E(H) W(x_v,x_w) Π_v ∈ V(H) dx_v.
Let G be a simple graph. The acyclic chromatic index χ_a'(G) of G is defined to be the least number of colors needed to color the edges of G so that no two edges coincident on the same vertex are homochromatic and there is no cycle whose edges are colored with only two colors.
Conjecture 1 (Bondy, 1980). Let k ≥ 1 and let G be a k-connected graph on n vertices. If δ(G) ≥ n + k(k-1)/k+1, then for every longest cycle C of G, every path in G - V(C) has at most k-1 vertices.
Does there exist an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors?
Conjecture 1.1 (Dean, 1988). For every integer k ≥ 3, every finite simple graph with minimum degree at least k contains a cycle whose length is divisible by k. A cycle has length at least 3, so the divisor is never 0 and the statement is not satisfied for a trivial reason.
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then R(k)/k2^k/2→ ∞.
Let R(k,l) be the usual Ramsey number: the smallest n such that if the edges of K_n are coloured red and blue then there exists either a red K_k or a blue K_l. Prove the existence of some c>0 such that lim_k→ inftyR(k+1,k)/R(k,k)> 1+c. A problem of Erdős and Sós.
Is there a constant c > 0 such that every graph on 2^n vertices with minimum degree > (1-c) · 2^n contains the n-dimensional hypercube Q_n? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal number of edges that guarantee a Q_n.
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
Let G be a graph with n vertices such that every induced subgraph on ≥ n/2 vertices has more than n^2/50 edges. Must G contain a triangle?
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c. The prize of 100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let m be sufficiently large and let G be a graph with m edges and no isolated vertices. Is the Ramsey number R(G) maximised when G is 'as complete as possible'?
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
Determine the Ramsey number R(C_4, S_n), where S_n=K_1,n is the star on n+1 vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Let δ > 0. If n is sufficiently large and G is a graph on n vertices with no K_2,2,2 (the octahedron) and at least δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
Erdős Problem 595 (\250): Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
The Erdős–Hajnal Conjecture states that there is a constant c(H) > 0 for each H such that we can take f(n) = n^c(H) in the above formulation.
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)∼ cn^α? The condition that G have at least two edges excludes degenerate forbidden graphs whose extremal number is eventually zero, for which the displayed asymptotic with c>0 is impossible.
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
Murty-Simon Conjecture Let G be a graph on n vertices with diameter 2 such that deleting any edge increases the diameter. Is it true that G has at most ⌊ n^2 / 4 ⌋ edges? Equality is conjectured to hold for the complete balanced bipartite graph K_⌈ n/2 ⌉, ⌊ n/2 ⌋.
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then find the value of lim_k→ inftyR(k)^1/k. This problem is #3 in Ramsey Theory in the graphs problem collection.
Let R(k) be the Ramsey number for K_k. Give a constructive proof that R(k) > C^k for some constant C > 1. Equivalently, give an explicit construction of graphs on n vertices which contain no clique and no independent set of size ≥ c log n, for some constant c > 0.
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Is it true that every subgraph of Q_n with ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.
For A⊆ 1,…,n let G(A) be the graph with vertex set A, where two integers are joined by an edge if they are coprime. Is it true that if |A| > ⌊ n/2 ⌋ + ⌊ n/3 ⌋ - ⌊ n/6 ⌋ then G(A) contains all odd cycles of length ≤ n/3 + 1? A problem of Erdős and Sárközy [ErSa97].
Erdős Problem #918
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T via cyclic shifts of a single embedding.
The Latin Tableau Conjecture: If G is the simple graph of a Young diagram, then G is CDS-colorable.
The pebbling number conjecture: the pebbling number of a Cartesian product of connected graphs is at most equal to the product of the pebbling numbers of the factors. See Asplund, Hurlbert, and Kenter.
For a graph G, we define Δ(G) to be the maximum degree, ω(G) to be the size of the largest clique subgraph, and χ(G) to be the chromatic number. Reed's omega, delta, and chi conjecture states that χ(G) ≤ ⌈ 1/2(ω(G) + Δ(G) + 1) ⌉.
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T. A "copy" of T is the image T.map(f_i) of T under a vertex embedding f_i : V hookrightarrow Fin(2n+1); the copies are pairwise edge-disjoint and together cover every edge of K_2n+1.
Sidorenko's conjecture (1993). For every finite bipartite simple graph H and every finite simple graph G: t(H, G) ≥ t(K_2, G)^e(H), where K_2 denotes the single-edge graph on 2 vertices (i.e. completeGraph (Fin 2)).
Conjecture 4 (Alon-Tarsi, 1985). Every bridgeless graph has a list of cycles covering every edge, with Σ_C |E(C)| ≤ 7/5|E(G)|.
Sheehan's conjecture (1977). Every 4-regular graph with a Hamiltonian cycle has a second Hamiltonian cycle (one with a different edge set).
TxGraffiti Conjecture 2: for every connected graph G with Δ(G) ≤ 3 and G ≠ K_4, Z(G) ≤ α(G) + 1. This conjecture is open.
TxGraffiti Conjecture 3: for every r-regular graph G (r ≥ 1), i(G) ≤ μ^(G). This conjecture is open**.
Vizing's conjecture (1968). For all finite simple graphs G and H, the domination number of the Cartesian (box) product satisfies γ(G square H) ≥ γ(G) γ(H).
WOWII Conjecture 100 (status O): For a simple connected graph G, α(G) ≤ ⌈(max_v l(v) + 0.5 · degreeL2Norm(Gᶜ)) / 2⌉ where α(G) = G.indepNum is the independence number, max_v l(v) is the maximum over all vertices of the independence number of the neighbourhood (in G), and degreeL2Norm(Gᶜ) is the…
WOWII Conjecture 133: For a simple connected graph G, path(G) ≥ rad(G) + (avg_v l(v))^cC_4(G), where path(G) is the path number of the graph (number of vertices of a largest induced path), rad(G) is the radius (minimum eccentricity, as a natural number), avg_v l(v) = l(G) is the average…
WOWII Conjecture 19 If G is connected then the size b(G) of a largest induced bipartite subgraph satisfies b(G) ≥ FLOOR((∑ ecc(v))/(|V|) + sSup (range (l G))), where ecc(v) denotes eccentricity and l(G) is the independence number of neighbourhoods.
WOWII Conjecture 198a For a simple connected graph G, if b(G) ≤ 2 + ecc_avg(G), then G has a Hamiltonian path. Here b(G) is the number of vertices in a largest induced bipartite subgraph, and ecc_avg(G) is the average eccentricity of G.
WOWII Conjecture 61 For a simple connected graph G, the size f(G) of a largest induced forest satisfies f(G) ≥ residue(G) + ⌈ diam(G) / 3 ⌉, where residue(G) is the Havel-Hakimi residue and diam(G) is the diameter of G.
Everything is published under CC BY 4.0 with authorship recorded. How it works
