Graph Theory problems

This area contains 92 revision-pinned source placements and 1 reviewed canonical dossiers. Placements may include aliases or duplicate claims.

Reviewed dossiers

• Hadwiger conjecture

Source placement records

• Babai's problem
• Brouwer's conjecture on upper bounds for sums of eigenvalues of Laplacians of graphs in terms of their number of edges
• γ–θ conjecture
• Graham's pebbling conjecture on the pebbling number of Cartesian products of graphs
• Meyniel's conjecture that cop number is O ( n ) {\displaystyle O({\sqrt {n}})} {\displaystyle O({\sqrt {n}})}
• vertex coloring game
• 1-factorization conjecture
• The perfect 1-factorization conjecture that every complete graph on an even number of vertices admits a perfect 1-factorization.
• Cereceda's conjecture on the diameter of the space of colorings of degenerate graphs
• The Earth–Moon problem
• The Erdős–Faber–Lovász conjecture on coloring unions of cliques
• The graceful tree conjecture that every tree admits a graceful labeling
• Rosa's conjecture that all triangular cacti are graceful or nearly-graceful
• The Gyárfás–Sumner conjecture on χ-boundedness of graphs with a forbidden induced tree
• The Hadwiger conjecture relating coloring to clique minors
• The Hadwiger–Nelson problem on the chromatic number of unit distance graphs
• Jaeger's Petersen-coloring conjecture
• The list coloring conjecture
• overfull conjecture
• The total coloring conjecture of Behzad and Vizing that the total chromatic number is at most two plus the maximum degree
• The Albertson conjecture
• Conway's thrackle conjecture that thrackles cannot have more edges than vertices
• GNRS conjecture
• Harborth's conjecture
• Negami's conjecture on projective-plane embeddings of graphs with planar covers
• The strong Papadimitriou–Ratajczak conjecture
• Turán's brick factory problem
• Guy's conjecture on the crossing number for complete graphs
• Universal point sets of subquadratic size for planar graphs
• conference graph
• Conway's 99-graph problem
• Degree diameter problem
• apex graph
• Moore graph
• strongly regular
• Barnette's conjecture
• Gilbert–Pollak conjecture
• Chvátal's toughness conjecture, that there is a number t such that every t-tough graph is Hamiltonian
• The cycle double cover conjecture
• The Erdős–Gyárfás conjecture on cycles with power-of-two lengths in cubic graphs
• The Erdős–Hajnal conjecture on large cliques or independent sets in graphs with a forbidden induced subgraph
• The Grünbaum–Nash-Williams conjecture on whether every 4-vertex-connected toroidal graph has a Hamiltonian cycle.
• The linear arboricity conjecture on decomposing graphs into disjoint unions of paths according to their maximum degree
• The Lovász conjecture on Hamiltonian paths in symmetric graphs
• Oberwolfach problem
• pathwidth
• reconstruction conjecture
• The snake-in-the-box problem
• Sumner's conjecture
• Szymanski's conjecture
• Tuza's conjecture
• The unfriendly partition conjecture
• Vizing's conjecture on the domination number of cartesian products of graphs
• Walescki's theorem for hypergraphs
• Zarankiewicz problem
• representation
• Characterise (non-)word-representable planar graphs
• Characterise word-representable graphs in terms of (induced) forbidden subgraphs.
• word-representable
• represented
• bipartite graphs
• line graph
• representing
• Delta-conjecture (1978)
• The imbalance conjecture
• The implicit graph conjecture on the existence of implicit representations for slowly-growing hereditary families of graphs
• Ryser's conjecture relating the maximum matching size and minimum transversal size in hypergraphs
• The second neighborhood problem
• Sidorenko's conjecture on homomorphism densities of graphs in graphons
• Teschner's bondage number conjecture
• every bridgeless graph has a nowhere-zero 5-flow
• every Petersen-minor-free bridgeless graph has a nowhere-zero 4-flow
• Woodall's conjecture
• Kahn–Kalai conjecture (Jinyoung Park and Huy Tuan Pham, 2022)
• Blankenship–Oporowski conjecture
• Ringel's conjecture
• Disproof of Hedetniemi's conjecture on the chromatic number of tensor products of graphs (Yaroslav Shitov, 2019)
• Kelmans–Seymour conjecture (Dawei He, Yan Wang, and Xingxing Yu, 2020)
• Goldberg–Seymour conjecture (Guantao Chen, Guangming Jing, and Wenan Zang, 2019)
• Babai's problem (Alireza Abdollahi, Maysam Zallaghi, 2015)
• Alspach's conjecture (Darryn Bryant, Daniel Horsley, William Pettersson, 2014)
• Alon–Saks–Seymour conjecture (Hao Huang, Benny Sudakov, 2012)
• Scheinerman's conjecture (Jeremie Chalopin and Daniel Gonçalves, 2009)
• Erdős–Menger conjecture (Ron Aharoni, Eli Berger 2007)
• Road coloring conjecture (Avraham Trahtman, 2007)
• Robertson–Seymour theorem (Neil Robertson, Paul Seymour, 2004)
• Strong perfect graph conjecture (Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas, 2002)
• Toida's conjecture (Mikhail Muzychuk, Mikhail Klin, and Reinhard Pöschel, 2001)
• Harary's conjecture on the integral sum number of complete graphs (Zhibo Chen, 1996)