Most pages in this directory have not yet been created; so far this is mostly
a list of some well-known problems for which more detailed pages will be
written later. **Its accessibility at this early stage is a plea for
contributed material to accelerate its development. **
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.

Alternatively, below is a direct search, courtesy of Google.
The code provided no longer works as it should, but it has been modified
to search in the domain www.math.uiuc.edu. Thus it will usually return some
pages that you have no interest in, but it will also find problem pages under
this one that contain your search term.

Note: Here is a discussion of the notation
for the number of vertices and the number of edges of a graph *G*.

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

- 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)

- Erdős-Faber-Lovász Conjecture (every union
of
*n*pairwise edge-disjoint copies of*K*is_{n}*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*such that every graph_{T}*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)

- 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 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)

- Jaeger's Conjecture, special case (every planar graph with girth at least
*4k*is*C*-colorable)_{2k+1} - 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*-colorable?)_{2k+1}

*L(2,1)*-labeling (every graph with maximum degree*k*can be colored with colors 0,...,*k*^{2}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*with_{k,k}*k*odd)

- Erdős-Sós Conjecture (every graph with average degree greater than
*m-1*contains every tree with*m*edges)

- Gallai's Conjecture (every
*n*-vertex graph decomposes into*⌈n/2⌉*paths) - Hajós' Conjecture (every even
*n*-vertex graph decomposes into*⌊n/2⌋*cycles) - Linear Arboricity Conjecture (every graph decomposes into
*⌈(Δ(G)+1)/2⌉*unions of disjoint paths) - Favaron-Genest-Kouider Conjecture [2010] (every
*(2k+1)*-regular graph having a perfect matching decomposes into paths with*2k+1*edges; proved for*k=1*by Kotzig, for*k=2*in the triangle-free case by Botler-Mota-Wakabayashi [2015]) - Nash-Williams Conjecture [1970] (for sufficiently large
*n*, every*n*-vertex graph with vertex degrees even, number of edges divisible by*3*, and minimum degree at least*3n/4*decomposes into triangles

- Kelly-Ulam Reconstruction Conjecture (every graph with at least 3 vertices is reconstructible from its deck of single vertex-deleted subgraphs)

- Ringel Tree Decomposition Conjecture (if
*T*is a tree of order*n*, then*K*decomposes into copies of_{2n-1}*T* - Tree Packing Conjecture (any trees of sizes
*1,...,n-1*decompose*K*)_{n} - Alspach's Conjecture (if
*n*is odd and*c*are integers between 3 and_{1},...,c_{m}*n*that sum to*(*, then_{2}^{n})*K*decomposes into cycles of lengths_{n}*c*)_{1},...,c_{m} - Hoffman-Singleton packing (does
*K*decompose into 7 copies of the Hoffman-Singleton graph?)_{50}

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

- 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)

- Sumner's Universal Tournament Conjecture
(every tournament of order
*2n-2*contains every oriented tree of order*n*)

- Jaeger's Dual-Hamiltonian Conjecture (every cyclically 4-connected cubic
graph
*G*has a bond of size*e(G)-n(G)+2*; equivalently, every cylically 4-connected cubic graph decomposes into two trees)

- Caccetta-Häggkvist Conjecture (every simple
*n*-vertex digraph with minimum outdegree at least*r*has a cycle of length at most the ceiling of*n/r*) - Bermond-Thomassen Conjecture [1981] on Disjoint Cycles (every simple
digraph with minimum outdegree at least
*2k-1*has*k*disjoint cycles)

- Erdős-Gyárfás Conjecture (every graph with minimum degree 3 has a cycle whose length is a power of 2)

- Fu-Huang-Rodger Conjecture (every
(
*k,g*)-cage is*k*-connected) - Bipartite Cage Conjecture (every cage with even girth is bipartite; Pisanski-Boben-Marusic-Orabnic-Graovac)

- Hitting all longest paths (does every chordal
graph have a vertex that appears in all longest paths?
What is the largest
*q*such that in every connected graph, every set of*q*longest paths have a common vertex?)

- Chvatal's Conjecture (some value of toughness is a sufficient to force a spanning cycle)
- Barnette's Conjecture (every planar 3-connected 3-regular bipartite graph is Hamiltonian)
- Seymour's
*k*th-power Hamiltonian Cycle Conjecture (every*n*-vertex graph with minimum degree at least*kn/(k+1)*contains*C*)_{n}^{k} - Zhang's Hamiltonian weight conjecture
(every 3-regular graph having a Hamiltonian weight arises from
*K*via Delta-Wye operations)_{4}

- Nash-Williams' Conjecture (every
*2k*-regular graph with at most*4k+1*vertices has a Hamiltonian decomposition) - Bermond's Conjecture (the cartesian product of two graphs having decompositions into Hamiltonian cycles also has such a decomposition)

- Induced forests in planar graphs (does every planar subgraph have an induced forest with at least half of the vertices? an induced linear forest with at least 4/9 of the vertices?)

- cyclic edge-connectivity of planar graphs (what is the maximum cyclic edge-connectivity of a 5-connected planar graph?) SOLVED! Borodin determined the answer to be 11 (see the link for further details).

- Zarankiewicz Conjecture (cr(
*K*) =_{m,n}*⌊m/2⌋⌊(m-1)/2⌋⌊n/2⌋⌊(n-1)/2⌋*) - cr(
*K*) =_{n}*¼⌊n/2⌋⌊(n-1)/2⌋⌊(n-2)/2⌋⌊(n-3)/2⌋* - Crossing number of cartesian product of
*C*and_{m}*C*is_{n}*m(n-2)*for*m≤n* - Are the pair-crossing number, the odd-crossing number, and the independent odd-crossing number always equal to the crossing number? (No, the odd-crossing number can be smaller)

- Tutte's 3-flow Conjecture (every 4-edge-connected graph is 3-flowable)
- Tutte's 4-flow Conjecture (every 2-edge-connected graph containing no Petersen-subdivision is 4-flowable)
- Tutte's 5-flow Conjecture (every 2-edge-connected graph is 5-flowable)

- Strong Embedding Conjecture (every 2-connected graph has an embedding on some orientable surface such that every face boundary is a cycle)
- Cycle Double Cover Conjecture (every 2-edge-connected graph has an exact double covering of its edges by cycles)
- Fulkerson (or Berge-Fulkerson) Conjecture (Archdeacon, Mohar) (every 2-connected 3-regular graph has an exact double covering of its edges by six matchings)

- Nedela-Skoviera Conjecture (every irreducible snark has girth at most 6)
- Jaeger-Swart Conjecture (every snark has cyclic edge-connectivity at most 6)

- Saturated Partitions & LYM orders (does every LYM order have a chain
partition that is
*k*-saturated for every*k*?) - L(m,n) (does the poset consisting of nondecreasing nonnegative integer
*m*-tuples bounded by*n*, ordered by inclusion, have a symmetric chain decomposition?)

- Removable Pair Conjecture (every poset has two points whose removal drops the dimension by at most 1)
- Kelly-Trotter Product Conjecture (
*dim(P x Q)≥dim(P)+dim(Q)-2*)

- 1/3-2/3 Conjecture (every non-chain poset has two elements
*x*and*y*such that the fraction of the linear extensions with*x*above*y*is between 1/3 and 2/3)

- Chvatal's Conjecture (in every ideal of sets, the largest intersecting family consists of the sets containing one specified element)

- Frankl's Union-Closed Set Conjecture (for
every family of subsets of
*[n]*that is closed under taking unions, there is an element of*[n]*appearing in at least half of the sets)

- The Pancake Problems (what is the worst-case
number of prefix reversals needed to sort a permutation (or a signed
permutation) of [
*n*]?)

- Determinant of Random Symmetric Matrices (what
is the typical value of the determinant of a symmetric
*n*-by-*n*random matrix whose entries are Bernoulli random variables with values 1 or -1?)

- Diagonal Ramsey Problem (is there a limit for log
*(R(k,k))/k*, and if so, what is it?)

- Revolving Door (Middle Levels) Conjecture
(there is a cycle through the subsets of [
*2k+1*] with sizes*k*and*k+1*by adding or deleting one element at each step) --- UPDATE: This has been proved by Torsten Mütze - Traversal by Prime Sum (for
*m≥2*, does the graph with vertex set [*2m*] and edges joining numbers whose sum is prime always have a Hamiltonian cycle?)