| Every graph with minimum degree 3 contains a cycle whose length is a power of 2. |
Erdős-Gyárfás conjecture (Erdős prize problem) (1995) |
4 |
3 |
open |
0 |
| Determine the minimum order of a connected graph whose line graph has signature t, for each t at least 2. |
arXiv link pending (2026) |
1 |
4 |
open |
0 |
| Every oriented graph has a vertex whose second out-neighborhood is at least as large as its first. |
Seymour's second neighborhood conjecture (posed c. 1990; see Dean-Latka) (1990) |
4 |
3 |
open |
0 |
| Sidorenko's conjecture in its smallest unresolved instance: the bipartite graph K(5,5) minus a 10-cycle satisfies the Sidorenko density inequality. |
Sidorenko's conjecture (smallest open case) (1993) |
4 |
2 |
open |
0 |
| For r-regular graphs (r at least 3), the independent domination number is at most the minimum maximal matching number. |
Machine-generated conjecture (TxGraffiti program), surveyed in 'In Reverie Together' (2025) (2020) |
1 |
4 |
open |
0 |
| For connected subcubic graphs other than K4, the zero forcing number is at most the independence number plus one. |
Machine-generated conjecture (TxGraffiti program), surveyed in 'In Reverie Together' (2025) (2017) |
1 |
4 |
open |
0 |
| In any finite union-closed family of sets (other than the empty family), some element belongs to at least half the sets. |
Union-closed sets conjecture (Frankl) (1979) |
5 |
1 |
open |
0 |
| Domination numbers satisfy γ(G□H) ≥ γ(G)γ(H) for the Cartesian product of any two graphs. |
Some unsolved problems in graph theory (Vizing) (1968) |
5 |
2 |
open |
0 |