Category
Problem Set
Status
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?...
Teschner's Bondage Number Conjecture
Is the bondage number of a graph always ≤ 3Δ/2, where Δ is the maximum degree?...
Tutte's 5-Flow Conjecture
Does every bridgeless graph have a nowhere-zero 5-flow?...
Tutte's 4-Flow Conjecture for Petersen-Minor-Free Graphs
Does every Petersen-minor-free bridgeless graph have a nowhere-zero 4-flow?...
Woodall's Conjecture
Is the minimum dicut size equal to the maximum number of disjoint dijoins in a directed graph?...