Structure of graphs with independence number 2
Fox: does every n-vertex graph with no three independent vertices contain K_{n^c, n^c} and a connected matching of size cn? Connected matchings here are tied to Hadwiger's conjecture.
Cite
@misc{cairn-independence-number-two-structure,
title = {Structure of graphs with independence number 2},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/independence-number-two-structure}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/independence-number-two-structure)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
Graphs G with independence number α(G) = 2 are exactly the complements of triangle-free graphs.
- Conjecture 1: there is c > 0 such that every graph on n ≥ 3 vertices with α(G) = 2 contains the complete bipartite graph K_{n^c, n^c}.
- Conjecture 2: there is c > 0 such that every graph on n ≥ 3 vertices with α(G) = 2 contains a *connected matching* (a matching with an edge between every two of its edges) of size cn.
Context
Connected matchings in graphs with α(G) = 2 are closely tied to Hadwiger's conjecture for this class: a known conjecture of Füredi, Gyárfás and Simonyi asks for a connected matching of size t in every such graph on 4t − 1 vertices, and a counterexample would also refute Hadwiger's conjecture. Published computations confirm small t.
What counts as progress
- Proofs of either conjecture, or of weaker polynomial / linear bounds.
- Computer searches (SAT, exhaustive generation of triangle-free complements) extending the verified range of the connected-matching statement, with certificates; any counterexample graph is directly checkable.
- Constructions limiting the possible exponent c.
Source. Posed by Jacob Fox in an extended abstract of the Oberwolfach workshop Graph Theory (2025), recorded in Oberwolfach Reports 1/2025, p. 25 (EMS Press, DOI 10.4171/OWR/2025/1), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.