Category
Problem Set
Status
Graph Coloring Game Monotonicity
If Alice has a winning strategy for the vertex coloring game with k colors, does she have one for k+1 colors?...
1-Factorization Conjecture
Does every k-regular graph on 2n vertices admit a 1-factorization when k ≥ n (or k ≥ n-1 for even n)?...
Perfect 1-Factorization Conjecture
Does every complete graph on an even number of vertices admit a perfect 1-factorization?...
Cereceda's Conjecture
For k-degenerate graphs, can any (k+2)-coloring be transformed to any other in polynomial steps via single-vertex recolorings?...
Earth-Moon Problem
What is the maximum chromatic number of biplanar graphs?...
Gyárfás-Sumner Conjecture
Is every graph class defined by excluding one fixed tree as an induced subgraph χ-bounded?...
Jaeger's Petersen Coloring Conjecture
Does every bridgeless cubic graph have a cycle-continuous mapping to the Petersen graph?...
List Coloring Conjecture
For every graph, does the list chromatic index equal the chromatic index?...
Overfull Conjecture
Is a graph with maximum degree Δ(G) ≥ n/3 in class 2 if and only if it has an overfull subgraph with the same maximum degree?...
Total Coloring Conjecture
Is the total chromatic number of every graph at most Δ + 2, where Δ is the maximum degree?...
Albertson Conjecture
Can the crossing number of a graph be lower-bounded by the crossing number of a complete graph with the same chromatic number?...
Conway's Thrackle Conjecture
Does every thrackle have at most as many edges as vertices?...
GNRS Conjecture
Do minor-closed graph families have $\ell_1$ embeddings with bounded distortion?...
Harborth's Conjecture
Can every planar graph be drawn with integer edge lengths?...
Negami's Conjecture
Does every graph with a planar cover have a projective-plane embedding?...
Turán's Brick Factory Problem
What is the minimum crossing number of the complete bipartite graph $K_{m,n}$?...
Guy's Crossing Number Conjecture
Is the crossing number of the complete graph $K_n$ equal to the value given by Guy's formula?...
Universal Point Sets
Do planar graphs have universal point sets of subquadratic size?...
Conference Graph Existence
Does there exist a conference graph for every number of vertices $v > 1$ where $v \equiv 1 \pmod{4}$ and v is an odd sum of two squares?...
Conway's 99-Graph Problem
Does there exist a strongly regular graph with parameters (99,14,1,2)?...
Degree Diameter Problem
For given maximum degree d and diameter k, what is the largest possible number of vertices in a graph?...
Moore Graph Existence
Does a Moore graph with girth 5 and degree 57 exist?...
Barnette's Conjecture
Does every cubic bipartite three-connected planar graph have a Hamiltonian cycle?...
Chvátal's Toughness Conjecture
Is there a constant t such that every t-tough graph is Hamiltonian?...
Cycle Double Cover Conjecture
Does every bridgeless graph have a collection of cycles that covers each edge exactly twice?...
Erdős-Gyárfás Conjecture
Does every graph with minimum degree 3 contain cycles of lengths that are powers of 2?...
Erdős-Hajnal Conjecture
Does every graph family defined by a forbidden induced subgraph have polynomial-sized cliques or independent sets?...
Linear Arboricity Conjecture
Can every graph with maximum degree Δ be decomposed into at most ⌈(Δ+1)/2⌉ linear forests?...
Lovász Conjecture
Does every finite connected vertex-transitive graph contain a Hamiltonian path?...
Oberwolfach Problem
For which 2-regular graphs H can the complete graph be decomposed into edge-disjoint copies of H?...
Cubic Graph Pathwidth
What is the maximum pathwidth of an n-vertex cubic graph?...
Snake-in-the-Box Problem
What is the longest induced path in an n-dimensional hypercube graph?...
Sumner's Conjecture
Does every (2n-2)-vertex tournament contain every n-vertex oriented tree?...
Tuza's Conjecture
Can the edges of any graph be covered by at most 2ν triangles, where ν is the maximum size of a triangle packing?...
Unfriendly Partition Conjecture
Does every countable graph admit a partition where every vertex has at least as many neighbors outside its part as inside?...
Zarankiewicz Problem
What is the maximum number of edges in a bipartite graph on (m,n) vertices with no complete bipartite subgraph $K_{s,t}$?...
Vizing's Conjecture
For the Cartesian product of graphs $G \square H$, is the domination number at least $\gamma(G) \cdot \gamma(H)$?...
Hamiltonian Decomposition of Hypergraphs
Do complete k-uniform hypergraphs admit Hamiltonian decompositions into tight cycles?...
Word-Representable Graphs: Letter Copies Bound
Are there graphs on n vertices requiring more than floor(n/2) copies of each letter for word-representation?...
Characterization of Word-Representable Planar Graphs
Characterize which planar graphs are word-representable....
Word-Representable Graphs: Forbidden Subgraph Characterization
Characterize word-representable graphs in terms of forbidden induced subgraphs....
Word-Representable Near-Triangulations
Characterize word-representable near-triangulations containing K₄....
Representation Number 3 Classification
Classify graphs with representation number exactly 3....
Crown Graphs and Longest Word-Representants
Among bipartite graphs, do crown graphs require the longest word-representants?...
Line Graphs of Non-Word-Representable Graphs
Is the line graph of a non-word-representable graph always non-word-representable?...
Translating Graph Problems to Word Problems
Which hard graph problems can be efficiently solved by translating graphs to their word representations?...
Imbalance Conjecture
If every edge has imbalance ≥1, is the multiset of edge imbalances always graphic?...
Implicit Graph Conjecture
Do slowly-growing hereditary graph families admit implicit representations?...
Ryser's Conjecture
For r-partite r-uniform hypergraphs, is the vertex cover number at most (r-1) times the matching number?...
Second Neighborhood Problem
Does every oriented graph have a vertex with at least as many vertices at distance 2 as at distance 1?...