Graph-theory open problems

Seagull problem

OPG_seagull_independence_2_clique_minor_half_n

Source: Open Problem Garden: seagull_problem

High ★★★ Graph Theory » Basic Graph Theory » Minors
Author: Seymour, Paul D.— posted by mdevos on 2008-01-06

Status ai-disproved high confidence

OpenAI's counterexample to Hadwiger's conjecture consists of $m$-vertex graphs with no independent set of size 3 whose largest clique minor has fewer than $26m/75 + 2/3 < m/2$ vertices. The manuscript notes that this is the Plummer–Stiebitz–Toft form of Hadwiger's conjecture for independence number 2.

Cited literature (2)

  • partial Packing seagulls (2012)
    Maria Chudnovsky, Paul Seymour · Combinatorica · doi:10.1007/s00493-012-2594-2

    Characterizes exactly when an $n$-vertex graph with no independent set of size 3 contains $k$ vertex-disjoint seagulls (induced 3-vertex paths), providing a polynomial-time algorithm and advancing structural understanding central to the seagull conjecture.

  • partial Dense minors of graphs with independence number two (2022)
    Sergey Norin, Paul Seymour · arXiv preprint · arXiv:2206.00186

    Proves that every $n$-vertex graph with $\alpha(G) \le 2$ contains an $\lceil n/2 \rceil$-vertex simple minor with $\approx 0.98688\binom{\lceil n/2 \rceil}{2} - o(n^2)$ edges, establishing a dense (but not complete) minor on exactly the number of vertices required by the seagull conjecture.

Reviewer notes. Literature status before this model-generated claim: partial. The seagull conjecture — every $n$-vertex graph with $\alpha(G) \le 2$ contains $K_{\lceil n/2 \rceil}$ as a minor — remains open. Norin and Seymour (2022) proved that every such graph contains an $\lceil n/2 \rceil$-vertex simple minor with approximately $0.98688\binom{\lceil n/2 \rceil}{2} - o(n^2)$ edges, establishing a nearly-complete minor on the right number of vertices but falling short of a complete minor. Chudnovsky and Seymour (2012) gave a complete characterization of when such graphs contain $k$ vertex-disjoint seagulls, a foundational packing result closely related to the minor problem.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Family 157: Graph coloring, clique minors, and Colin de Verdière invariants

Caveat. This manuscript lies outside the family's Lean formalization, which covers only the companion list-colouring bound.

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry partial. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. Every $ n $ vertex graph with no independent set of size $ 3 $ has a complete graph on $ \ge \frac{n}{2} $ vertices as a minor.
Keywords: coloring · complete graph · minor

Discussion

This conjecture is significant because it is an interesting unproved consequence of Hadwiger's conjecture (this implication is proved next). In fact, some experts have suggested that this problem might hold the key to finding a counterexample to Hadwiger. I (M. DeVos) have attributed this conjecture to Seymour, but I believe that it may have been independently suggested by Mader and by others. Its curious title will be explained later in this discussion. Hadwiger's conjecture (every loopless graph with chromatic number $ \ge n $ has $ K_n $ as a minor) is one of the outstanding problems in graph theory. This conjecture has been resolved for small values of $ n $ ; when $ n \le 4 $ it is relatively easy, for $ n=5,6 $ it has been proven to be equivalent to the Four color theorem. The Seagull problem concerns the other extreme - when the size of the chromatic number is close to the order of the graph. If $ G $ is an $ n $ vertex graph with no independent set of size 3, then $ \chi(G) \ge \frac{n}{2} $ since each color class has size $ \le 2 $ . If Hadwiger's conjecture holds for $ G $ , it must then have a minor which is a complete graph on $ \ge \frac{n}{2} $ vertices. This is precisely the statement of the Seagull problem. The (essentially) best known bound for the conjecture is that every $ n $ vertex graph $ G $ with no independent set of size 3 has a complete graph on $ \ge \frac{n}{3} $ vertices as a minor. This argument is where the name of this conjecture arises. Let us call a seagull of $ G $ an induced subgraph which is a 2-edge path (such a subgraph may be drawn suggestively as a seagull). Then, for every seagull $ S $ and every vertex $ v $ not in $ S $ , there must be an edge between $ v $ and one of the two endpoints of $ S $ (this follows from the assumption that $ G $ has no independent set of size 3). This feature makes seagulls especially useful for constructing complete graphs as minors - as we now demonstrate. Choose a maximal collection $ {\mathcal S} $ of pairwise disjoint seagulls of $ G $ . The graph $ G' $ obtained from $ G $ by deleting every vertex which appears in a seagull in $ {\mathcal S} $ cannot have any two vertices at distance 2 from one another (since this would yield a seagull), so $ G' $ must be a disjoint union of complete graphs. Since $ G' $ has no independent set of size 3, it is in fact a disjoint union of at most two complete graphs. By deleting every vertex in the smaller complete subgraph of $ G' $ from $ G $ and then contracting both edges in every seagull in $ {\mathcal S} $ , we obtain a complete graph minor of $ G $ with size $ \ge \frac{n}{3} $ . Kawarabayashi, Plummer, and Toft have improved this bound slightly by showing that $ G $ must have a complete graph minor of size $ \ge \frac{n + \omega(G)}{3} $ , but it looks very difficult to get much more out of this type of argument.

Bibliography

  • [KPT] K. Kawarabayashi, M. Plummer, and B. Toft, Improvements of the theorem of Duchet and Meynial's theorem on Hadwiger's Conjecture, J. Combin. Theory Ser. B. 95 (2005) 152-167.

Related conjectures

  • implied by Fractional Hadwiger open Part (a) of Fractional Hadwiger states chi_f(G) <= had(G). By LP duality (fractional covering by independent sets), chi_f(G) >= n/alpha(G) for every n-vertex G. If G has no independent set of size 3 then alpha(G) <= 2, so chi_f(G) >= n/2, whence had(G) >= n/2; since had(G) is an integer, G has a K_{ceil(n/2)} minor, i.e. a complete minor on >= n/2 vertices — exactly the Seagull problem. The source conjecture is the conjunction of (a),(b),(c), and (a) alone suffices, so the conjecture implies Seagull. (Part (b) alone would not obviously suffice, since had_f >= had; but the edge is from the full conjecture.) Direction correct: Fractional Hadwiger is the stronger statement.
  • implied by Hadwiger's conjecture ai-disproved Take an n-vertex graph with independence number at most 2. Every colour class has at most 2 vertices, so chi >= n/2, and Hadwiger then gives a K_{ceil(n/2)} minor. The target's own context proves this implication and calls the Seagull problem an unproved consequence of Hadwiger's conjecture.
  • implied by Independence number lower bound in K_{t+1}-minor-free graphs ai-disproved Let G be an n-vertex graph with alpha(G) <= 2 and let h = had(G) be the largest k with a K_k minor. Then G has no K_{h+1} minor, so the source conjecture with t = h gives alpha(G) >= n/h, hence 2 >= n/h and h >= n/2; as h is an integer, G has a K_{ceil(n/2)} minor, which is exactly the Seagull statement. Equivalently, Seagull is the alpha = 2 special case of the conjecture that K_{t+1}-minor-free graphs satisfy alpha >= n/t (both are standard weakenings of Hadwiger's conjecture via chi >= n/alpha resp. chi >= n/2). Parameters are monotone and the specialization is exact; direction as claimed, and all three finder sketches agree with this derivation.

View in the relation graph — relations are AI-reviewed, not formally verified.