Open Problems - Graph Theory and Combinatorics

collected and maintained by Douglas B. West

This directory mostly lists some well-known problems for which more detailed pages may be created later. The organization of topics roughly follows the four volumes of The Art of Combinatorics under development by D.B. West. Thus the four main headings are Extremal Graph Theory, Structure of Graphs, Order and Optimization, and Arrangements and Methods.

Note: Here is a discussion of the notation for the number of vertices and the number of edges of a graph G. Other directories of open problems pages can be found as follows: Graph Theory, Combinatorics, Optimization. (emphasizing graph theory, combinatorics, number theory, and discrete geometry) is at the Open Problem Garden at Simon Fraser University.

Extremal Graph Theory

Distance in graphs

• Maximum oriented diameter (for graphs with diameter k, how large can the smallest diameter of an orientation be?)

Average distance

• Average distance in vertex-transitive graphs (Alan Kaplan): (in a vertex-transitive graph, the average distance from a given vertex to the other vertices exceeds half the diameter; PROVED in a more general context by Mark Herman and Jonathan Pakianathan -- see arXiv article)

Matching and Independence

Coloring

• Erdős-Faber-Lovász Conjecture (every union of n pairwise edge-disjoint copies of K_n is n-colorable)
• Alon-Saks-Seymour Conjecture (every union of m pairwise edge-disjoint complete bipartite graphs is (m+1)-colorable - FALSE)
• Lovász Doubly Critical Graph Conjecture (if χ(G-x-y)=χ(G)-2 for every edge xy in G, then G is a complete graph)
• Gyárfás-Sumner Conjecture (for every forest T, there exists a function f_T such that every graph G with no induced subgraph isomorphic to T has chromatic number at most f(ω(G)))
• Reed's upper bound (for every graph G, the chromatic number is at most the ceiling of (1+Δ(G)+ω(G))/2
• Dense triangle-free graph conjecture (G is 4-colorable if G is triangle-free and δ(G)≥n(G)/3)
• Brandt's regular supergraph conjecture (every maximal triangle-free graph G with δ(G)≥n(G)/3 has a regular supergraph obtained by vertex multiplications)

Edge-coloring

• Goldberg-Seymour Conjecture (every multigraph G has a proper edge-coloring using at most max{μ(G),Δ(G)+1} colors, where μ(G) is the maximum of ⌈|E(H)|/(½(|V(H)|-1))⌉ over subgraphs H of G) with |V(H)| odd)
• Overfull Conjecture (Class 2 requires overfull subgraph when Δ(G)>n/3)
• 1-Factorization Conjecture (if G is a 2m-vertex regular graph with degree at least 2⌈m/2⌉-1, then G is 1-factorable --- implied by Overfull Conjecture)
• Total Coloring Conjecture (the vertices and edges of a graph G can be colored with Δ(G)+2 colors such that adjacent vertices have different colors, incident edges have different colors, and incident edge and vertices have different colors)
• Strong Chromatic Index (for edge-colorings in which distinct edges of the same color cannot have adjacent vertices, what are the best bounds on the number of colors needed in terms of the maximum degree?)

List Coloring

• List Coloring Conjecture (edge-choosability equals edge-chromatic number)
• Square List Coloring Conjecture (choosability equals chromatic number) for the square of every graph
• 4-Choosability of 5-connected planar graphs (would imply 4-color Theorem; all known planar graphs that are not 4-choosable are not 5-connected - Kawarabayashi-Toft)
• List coloring of locally sparse graphs (for graphs with maximum degree D and maximum codegree cD, choosability is bounded by (c+o(1))D, where the codegree of vertices u and v is their number of common neighbors)

Graph Homomorphism and Circular Coloring

• Jaeger's Conjecture, special case (every planar graph with girth at least 4k is C_2k+1-colorable)
• Albertson-Chan-Haas Problem (is it true that every n-vertex graph with odd girth at least 2k+1 and minimum degree greater than 3n/(4k) is C_2k+1-colorable?)

Generalized Coloring

Stronger Coloring Requirements

• L(2,1)-labeling (every graph with maximum degree k can be colored with colors 0,...,k² such that the colors on adjacent vertices differ by at least 2 and the colors on vertices at distance 2 differ by at least 1)
• Equitable Coloring Conjecture (a connected graph with maximum degree k has a proper k-coloring with color classes differing in size by at most 1 if and only if it is not an odd cycle, a complete graph, or the complete bipartite graph K_k,k with k odd)

Hypergraphs

Perfect Graphs and Related Families

Classical Extremal Problems

Structure of Graphs

Existence questions

• Ringel Tree Decomposition Conjecture (if T is a tree of order n, then K_2n-1 decomposes into copies of T
• Tree Packing Conjecture (any trees of sizes 1,...,n-1 decompose K_n)
• Alspach's Conjecture (if n is odd and c₁,...,c_m are integers between 3 and n that sum to (₂ⁿ), then K_n decomposes into cycles of lengths c₁,...,c_m)
• Hoffman-Singleton packing (does K₅₀ decompose into 7 copies of the Hoffman-Singleton graph?)

Labelings

• Kotzig-Ringel Graceful Tree Conjecture (every tree has a vertex numbering with 1,...,n such that n-1 distinct differences appear on the edges)

Packing

Vertex Degrees

• Seymour's 2nd Neighborhood Conjecture (in a digraph with no cycles of length at most 2, some vertex has at least as many vertices at distance 2 as at distance 1)