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.
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.
The weaker question from the same problem: is f_c(n) ≫ log n? Same feasibility bound on c as above.
Is it true that any K_r-free graph on n vertices with average degree t contains an independent set on ≫_r log t/tn many vertices? A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81].
For which functions g(n) with n>g(n)≥ (log n)^2 is there a graph on n vertices in which every induced subgraph on g(n) vertices contains a clique of size ≥ log n and an independent set of size ≥ log n? In particular, is there such a graph for g(n)=(log n)^3? This is the first part.
Let G be a chordal graph on n vertices - that is, G has no induced cycles of length greater than 3. Can the edges of G be partitioned into n^2/6+O(n) many cliques?
Does there exist some ε>0 such that, for all sufficiently large n, there exists a graph G on n vertices with at least ε n^2 edges whose edges can be coloured with n colours so that every C_4 receives four distinct colours?
Is it true that R(n+1)/R(n)≥ 1+c for some constant c>0, for all large n?
Let h(n) be minimal such that every graph on n vertices where every set of 7 vertices contains a triangle must contain a clique on at least h(n) vertices. Estimate h(n). In particular, do there exist constants c_1, c_2 > 0 such that n^1/3+c_1 ≪ h(n) ≪ n^1/2-c_2?
F(n) / log n → ∞ as n → ∞
Does there exist a k>2 such that the k-sized subsets of 1,...,2k can be coloured with k+1 colours such that for every A⊂ 1,…,2k with lvert Arvert=k+1 all k+1 colours appear among the k-sized subsets of A?
Let k≥ 2 and A_k⊆ [0,1] be the set of α such that there exists some β(α)>α with the property that, if G_1,G_2,… is a sequence of k-uniform hypergraphs with liminf e(G_n)/C(lvert G_nrvert, k) >α then there exist subgraphs H_n⊆ G_n such that lvert H_nrvert → ∞ and liminf e(H_n)/C(lvert H_nrvert, k)…
Is it true that, for all large n, f(n + 1) ≥ f(n)?
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.
Let f(n) be minimal such that there is a tournament (a complete directed graph) on f(n) vertices such that every set of n vertices is dominated by at least one other vertex. Estimate f(n).
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges that is Ramsey for G. Is there a function f such that f(x)/x→ ∞ as x→ ∞ such that, for all large C, if G is a graph with n vertices and e≥ Cn edges then hatR(G) > f(C) e?
Let k≥ 4 and f_k(n) be the largest number of edges in a graph on n vertices which has chromatic number k and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that f_6(n)∼ n^2/4? This is the second part.
Erdős Problem #918
Let h_t(d) be minimal such that every graph G with h_t(d) edges and maximal degree ≤ d contains two edges whose shortest path between them has length ≥ t. Estimate h_t(d). A problem of Erdős and Nešetřil [Er88].
Let k ≥ 4 and r≥ 1. Must there exist a graph G with chromatic number k such that every vertex is critical, yet every critical set of edges has size >r?
Let S ⊆ ℝ be a set containing no solutions to a + b = c. Must there be a set A ⊆ ℝ ∖ S of cardinality continuum such that A + A ⊆ ℝ∖ S?
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.
Lovász's conjecture (1970). Every finite connected vertex-transitive graph has a Hamiltonian path.
Meyniel's conjecture (c. 1985). There is a universal constant C such that every connected graph on n vertices has cop number at most C √n: a team of O(√n) cops can always catch the robber in the game of cops and robbers.
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.
Tournament Anti-Sidorenko (TAS) Trees Conjecture. For every finite undirected tree T, there exists an orientation vecT of its edges such that for any finite tournament G, the homomorphism density satisfies: t_vecT(G) ≤ 2^-e(T) where e(T) is the total number of edges in T.
Conjecture 4 (Alon-Tarsi, 1985), simple-graph specialization. Every bridgeless simple graph has a list of cycles covering every edge, with Σ_C |E(C)| ≤ 7/5|E(G)|.
The Berge–Fulkerson conjecture (Fulkerson 1971). Every bridgeless cubic graph has six perfect matchings such that every edge lies in exactly two of them.
The Bollobás–Eldridge–Catlin conjecture (1978). If G_1 and G_2 are graphs on the same n vertices with maximum degrees Δ_1, Δ_2 satisfying (Δ_1 + 1)(Δ_2 + 1) ≤ n + 1, then G_1 and G_2 pack.
The burning number conjecture (Bonato–Janssen–Roshanbin [BJR16]). Every connected graph on n vertices can be burned in at most ⌈√n⌉ rounds: fires started at one new vertex per round, each spreading to all neighbouring vertices every round, can burn the whole graph in ⌈√n⌉ rounds.
The Gyárfás–Sumner conjecture (Gyárfás 1975, Sumner 1981). For every finite tree T the class of T-free graphs (graphs with no induced subgraph isomorphic to T) is χ-bounded: there is a function f such that every T-free graph G satisfies χ(G) ≤ f(ω(G)).
The linear arboricity conjecture (Akiyama–Exoo–Harary [AEH81]). The edges of every graph of maximum degree Δ can be partitioned into at most ⌈(Δ + 1) / 2⌉ linear forests.
Sheehan's conjecture (1977). Every 4-regular graph with a Hamiltonian cycle has a second Hamiltonian cycle (one with a different edge set).
The Petersen colouring conjecture (Jaeger 1988). Every bridgeless cubic graph has a Petersen colouring: an edge colouring by the edges of the Petersen graph such that the three edges at each vertex are mapped onto the three edges at some vertex of the Petersen graph.
The total colouring conjecture (Behzad 1965, Vizing 1968). Every finite simple graph G has a total colouring with at most Δ(G) + 2 colours, i.e. χ''(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree.
Tuza's conjecture (1981): every finite graph G satisfies τ(G) ≤ 2ν(G), where τ(G) is its triangle covering number and ν(G) is its triangle packing number. The bound would be sharp, for example for K_4 and K_5.
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 189 (status O): For a simple connected graph G, if max_v distEven(v) ≤ 1 + σ(G), then G has a Hamiltonian path. Here distEven(v) is the number of vertices at even distance from v, and σ(G) is the second-smallest degree of G's degree sequence (per WOWII defEntry 65).
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 199 For a simple connected graph G, if tree(G) - 2 ≤ κ(G), then G has a Hamiltonian path. The nontrivial vertex type encodes the source assumption n > 1. Here tree(G) is the number of vertices in a largest induced tree and κ(G) = vertexConnectivity G is the vertex connectivity 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.
WOWII Conjecture 72 For a simple connected graph G, tree(G) ≥ ⌈ecc_avg(G) + max_v λ(v)/3⌉ where tree(G) is the number of vertices in a largest induced tree, ecc_avg(G) is the average eccentricity of G, and max_v l(v) = max_v indepNeighborsCard G v is the maximum over all vertices of the…
WOWII Conjecture 84 (status O): For a simple connected graph G with positive minimum degree, tree(G) ≥ 2 · rad(G) / δ(G), where tree(G) is the number of vertices in a largest induced subtree, rad(G) is the radius, and δ(G) = G.minDegree is the minimum degree.
WOWII Conjecture 96 For a simple connected graph G on at least two vertices, α(G) ≤ 1 + min_v distEven(v) · (max_v l(v) - 1) where α(G) = G.indepNum is the independence number, distEven(v) is the number of vertices at even distance from v, and max_v l(v) is the maximum independence number of a…
Everything is published under CC BY 4.0 with authorship recorded. How it works
