Graph Coloring

../

E0019/: Asks whether a graph made of n edge-disjoint copies of the complete graph on n vertices has chromatic number exactly n.

E0057/: Asks whether the reciprocals of the odd cycle lengths of a graph with infinite chromatic number must always sum to infinity.

E0058/: Asks whether a graph with odd cycles of at most k distinct lengths has chromatic number at most two k plus two, with equality only if it has a big clique.

E0063/: Asks whether every graph with infinite chromatic number contains a cycle whose length is a power of two, for infinitely many powers of two.

E0074/: Asks whether, for every function growing to infinity, some graph of infinite chromatic number has each n-vertex subgraph made bipartite by that many deletions.

E0075/: Asks whether some graph of chromatic number aleph-one on aleph-one vertices has every large n-vertex subgraph containing an independent set of size above n^(1-epsilon) for each epsilon > 0, and asks the same for linear size.

E0108/: Asks whether, for every girth bound at least 4 and every k, large enough chromatic number forces a subgraph of that girth with chromatic number at least k; disproved at girth 5 and k = 7 by a Lean counterexample family.

E0110/: Asks whether one function F(n) bounds, for all large n, the order of a smallest subgraph of chromatic number n in every graph of chromatic number aleph-one.

E0625/: Compares the cochromatic number, the fewest colors whose classes each induce a complete or empty graph, with the ordinary chromatic number.

E0626/: Asks whether the largest girth of a graph on n vertices with chromatic number k, divided by the logarithm of n, tends to a limit, for k at least four.

E0627/: Asks whether the largest ratio of chromatic to clique number on n vertices, divided by n over the squared logarithm of n, tends to a limit.

E0628/: Asks whether a graph of chromatic number k with no k-vertex clique has disjoint subgraphs of chromatic number at least a and at least b when a plus b is k+1.

E0629/: Asks for the least number of vertices n(k) of a bipartite graph whose list chromatic number exceeds k; open, with n(2) = 6 and n(3) = 14 known.

E0630/: Bounds the list chromatic number, the least list size per vertex always permitting a proper coloring from the lists, for graphs of a given kind.

E0631/: Asks whether every planar graph has list chromatic number at most 5, the least list size per vertex always allowing a proper coloring from the lists, and whether 5 is best possible.

E0632/: Asks whether choosability from lists of a colors with b chosen per vertex implies the same for other pairs of list size and choice size.

E0640/: Asks whether large enough chromatic number forces an odd cycle whose vertices span a subgraph of chromatic number at least k, for k at least three.

E0706/: Bounds the largest chromatic number of a graph on finitely many plane points whose edges join pairs at one of r prescribed distances.

E0736/: Asks whether a graph of chromatic number aleph one must, for every cardinal m, admit a graph of chromatic number m all of whose finite subgraphs occur in it.

E0737/: Asks whether a graph of chromatic number aleph one must contain an edge lying on a cycle of every sufficiently large length.

E0738/: Asks whether every triangle-free graph of infinite chromatic number contains every tree as an induced subgraph.

E0739/: Asks whether a graph of infinite chromatic number m must have a subgraph of chromatic number n for every infinite cardinal n below m.

E0740/: Asks whether a graph of infinite chromatic number m must contain a subgraph of the same chromatic number with no odd cycle of length at most r.

E0744/: Estimates the fewest edges whose deletion makes bipartite some n-vertex graph of chromatic number k in which every proper subgraph has smaller chromatic number.

E0750/: Asks, for any function tending to infinity, whether some graph of infinite chromatic number has every m-vertex subgraph containing a large independent set.

E0751/: Asks whether a graph of chromatic number four can have arbitrarily large gaps between consecutive cycle lengths, and whether this is possible with large girth.

E0753/: Asks whether some constant c > 0 makes the list chromatic numbers of every n-vertex graph and its complement sum to more than n^(1/2 + c).

E0758/: Determines the largest cochromatic number of an n-vertex graph, where each color class must induce a complete or an empty graph.

E0759/: Asks for the growth rate of the largest cochromatic number of a graph embeddable on the orientable surface of genus n, the cochromatic number being the fewest colors whose classes each induce a complete or an empty graph.

E0760/: Bounds the cochromatic number of a graph, the fewest colors needed so that every color class induces either a complete graph or an independent set.

E0761/: Asks how the least number of colors whose classes induce complete or empty graphs compares with the least number avoiding monochromatic oriented cycles.

E0762/: Asks whether a graph with no K_5 and cochromatic number at least 4 has chromatic number at most the cochromatic number plus 2; answered no by Steiner's 2024 graphs with clique number 4, cochromatic 4 and chromatic 7.

E0780/: Asks whether t-coloring the edges of the complete r-uniform hypergraph on enough vertices forces some color class to contain k pairwise disjoint edges; proved by Alon, Frankl and Lovász in 1986 (Lovász 1978 for k = 2).

E0797/: The largest number of colors needed to color any graph of maximum degree d so that no edge and no cycle uses only one or two colors respectively; of order d^{4/3} up to a (log d)^{1/3} factor by Alon, McDiarmid and Reed 1991.

E0799/: Asks whether almost every graph on n vertices has list chromatic number o(n); yes by Alon 1992 (O(n log log n / log n)), sharpened by Alon, Krivelevich and Sudakov 1999 to order n / log n.

E0832/: Records Alon's counterexamples to the complete-hypergraph edge benchmark, while separating the defective equality wording and the open r=3 case.

E0833/: Records the Erdős–Lovász exponential vertex-degree bound and an explicit constant that covers every uniformity r at least two.

E0836/: Separates the false vertex-bound question from the unresolved linear intersection question and repairs the site's chromatic-number gloss.

E0842/: Asks whether n disjoint triangles joined by a Hamiltonian cycle on their 3n vertices always give a 3-colorable graph; proved by Fleischner and Stiebitz.

E0917/: Separates the proved quadratic lower bound, open k=6 case, and disproved nonmultiples-of-three part of the proposed general asymptotic.

E0918/: Asks whether some graph has aleph two vertices and chromatic number aleph two while every subgraph on aleph one vertices is countably colorable.

E0919/: Asks whether some graph on the ordinal omega two squared has chromatic number aleph two while every subgraph of smaller type is countably colorable.

E0920/: The largest possible chromatic number of a graph on n vertices containing no complete graph on k vertices.

E0921/: Asks whether, for every k at least 4, the longest odd cycle avoidable in a k-chromatic graph on n vertices has length about the (k minus 2)th root of n.

E0922/: Asks whether a graph in which every subgraph on n vertices has an independent set of size at least (n minus k)/2 has chromatic number at most k plus 2.

E0923/: Asks whether every graph whose chromatic number is large enough in terms of k contains a triangle-free subgraph with chromatic number at least k.

E0944/: Asks whether for every k at least 4 and r at least 1 some k-chromatic graph has every vertex critical and no critical set of at most r edges; settled by a Lean proof the bounty site Conjectures.io certified in September 2026.

E1013/: Asks for an asymptotic formula for the fewest vertices of a triangle-free graph with chromatic number k, and for a proof that consecutive values have ratio tending to one.

E1032/: Concerns graphs of chromatic number four in which deleting any edge drops the chromatic number to three.

E1091/: Asks whether every graph with chromatic number four and no complete graph on four vertices contains an odd cycle with at least two diagonals; Erdős first asked for one diagonal, which Larson proved in 1979.

E1092/: Determines the largest f so that a graph whose every m-vertex subgraph is an r-colorable graph plus at most f edges has chromatic number at most r plus one.

E1104/: Estimates the largest chromatic number possible for a triangle-free graph on n vertices.

E1156/: Asks a question about the chromatic number of a random graph on n vertices in which each edge appears independently with probability one half.

---

Chromatic number of graphs and hypergraphs, list and edge colorings, color-critical graphs, and the interaction of coloring with girth and cycles; colorings of the plane and of R^n are filed with discrete geometry.

Site tags routed here: chromatic number, combinatorics, cycles, graph theory, hypergraphs.