Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Graph Coloring

adamczewski_2026_erdos74/: Gives the short-odd-walk and distance-band proof disproving the proposed almost-bipartite property for graphs of infinite chromatic number.

akdemir_2015_advances_defective_parameters_graphs/: Computer-assisted determination of the defective cochromatic thresholds c_0(4) = 12, c_1(3) = 12 and c_2(2) = 10, giving z(12) = 4 and z(13) = 5.

akhiiarov_2025_lower_bounds_independence_numbers_distance_graphs/: Proves new exponential lower bounds on independence numbers of one-distance graphs on ternary vectors across a wide linear range of parameters.

alesandroni_2021_erdos_faber_lovasz_conjecture_weakly/: Proves the Erdos-Faber-Lovasz conjecture for weakly dense hypergraphs, a class generalizing Sanchez-Arroyo's dense hypergraphs.

alon_1985_hypergraphs_high_chromatic_number/: Alon's published strict asymptotic improvement over the complete-hypergraph edge benchmark for hypergraphs of large uniformity and chromatic number.

alon_1986_chromatic_number_kneser_hypergraphs/: Proves Erdős's 1973 conjecture that a t-coloring of the r-subsets of an n-set with n >= kr + (t-1)(k-1) has k pairwise disjoint sets of one color, determining when Kneser hypergraphs are t-colorable, and bounds colorings avoiding k sets with small pairwise intersections.

alon_1991_acyclic_coloring_graphs/: Proves that the largest acyclic chromatic number of a graph of maximum degree d is O(d^{4/3}) and Omega(d^{4/3}/(log d)^{1/3}), settling Erdős's 1976 conjecture that it is o(d^2), with O(sqrt(gamma) d) for graphs without a K_{2,gamma+1} on a nonadjacent pair and O(d) acyclic edge colorings.

alon_1992_choice_numbers_graphs_probabilistic_approach/: Proves that the complete r-partite graph with m vertices in each class has choice number of order r log m, answering two questions of Erdos, Rubin and Taylor.

alon_1992_colorings_orientations_graphs/: Shows a digraph with unequal counts of even and odd Eulerian subgraphs admits a coloring from any lists of size one more than each vertex's outdegree, so every bipartite planar graph is 3-choosable.

alon_1997_subgraphs_large_cochromatic_number/: Proves every graph of chromatic number n has a subgraph of cochromatic number at least (1/4+o(1))n/log_2 n, settling an Erdos-Gimbel conjecture.

alon_1999_list_coloring_random_pseudo_random_graphs/: Proves that the choice number of the random graph G(n,p) is almost surely of order np/ln(np) whenever 2 < np <= n/2, using for dense p a deterministic bound for pseudo-random graphs.

araujo_2025_note_maximum_ratio_between_chromatic_number/: Improves the constant in the upper bound for the largest ratio of chromatic to clique number, the first such gain since 1967.

araujopardo_2016_note_erdos_faber_lovasz/: Verifies the Erdos-Faber-Lovasz conjecture for a new infinite family of hypergraphs using an arithmetic edge coloring of the complete graph.

berdnikov_2014_chromatic_number_euclidean_space_two_forbidden/: Gives a pairing method that turns lower bounds for 2k-distance graphs into asymptotic lower bounds for the chromatic number with two forbidden distances.

berdnikov_2016_estimate_chromatic_number_euclidean_space_several/: Proves that the chromatic number of Euclidean n-space with k forbidden distances, maximized over the distances, is at least (Bk)^(Cn) for all n and k, for every positive C below 1/3, where Raigorodskii's bound needed large n.

berdnikov_2018_chromatic_numbers_distance_graphs_several_forbidden/: Proves exponential lower bounds (Bk)^(Cn) for chromatic numbers of distance graphs in l_p^n with k forbidden distances and no clique of a fixed size.

bondy_1998_cycles_graph_lengths_differ_one_two/: Proves that every simple graph other than K1 and K2 with at most two vertices of degree below three has two cycles whose lengths differ by one or two, and that every nonbipartite 3-connected graph has two cycles whose lengths differ by one.

bruijn_1951_colour_problem_infinite_graphs_problem_theory/: Proves that a graph all of whose finite subgraphs are k-colorable is itself k-colorable, and applies this to independent sets in relations.

bucic_2020_intersection_spectrum_3_chromatic_intersecting_hypergraphs/: Bucić, Glock, and Sudakov lower-bound the number of distinct intersection sizes, with the exact arXiv artifact distinguished from the publication.

cherkashin_2020_regular_behavior_maximal_hypergraph_chromatic_number/: Proves Alon's conjecture that m(n,r)/r^n converges for each fixed n, where m(n,r) is the least edge count of a non-r-colorable n-uniform hypergraph.

chojecki_2026_note_n_1_epsilon_version_erdos/: Shows the classical Specker graph answers the weaker n to the one minus epsilon form of an Erdos-Hajnal-Szemeredi question on independence numbers.

chybowskasokol_2023_coloring_distance_graphs_plane/: Improves bounds on colorings of the plane forbidding all distances in an interval, and determines the chromatic number exactly on two ranges.

davies_2022_ramsey_problem_triangle_free_graphs/: Improves the upper bound on the chromatic number of triangle-free graphs on n vertices by a factor of the square root of two.

dvorak_2019_4_choosable_graph_not_8_2_choosable/: Exhibits a 4-choosable graph that is not (8:2)-choosable, answering in the negative the question of Erdős, Rubin and Taylor whether every (a:b)-choosable graph is (am:bm)-choosable.

erdos_1959_graph_theory_probability/: Uses a probabilistic argument to build graphs of high girth and high chromatic number, and bounds Ramsey numbers from below.

erdos_1961_graph_theory_probability/: Proves by a probabilistic construction that the Ramsey number f(3,l) exceeds a constant times l squared divided by a power of log l.

erdos_1967_kromatikus_grafokrol_chromatic_graphs/: Builds graphs of large chromatic number whose finite induced subgraphs all have large independent sets, using unit-sphere distance graphs.

erdos_1967_remarks_chromatic_graphs/: Shows the largest ratio of chromatic number to clique number over n-vertex graphs is of order n divided by log-squared n.

erdos_1968_chromatic_number_infinite_graphs/: Builds, for every infinite cardinal gamma and finite k >= 1, a graph on exp_{k-1}(gamma)^+ vertices with chromatic number above gamma whose subgraphs on at most exp_{k-1}(gamma) vertices are gamma-colourable, and poses the cases this leaves open.

erdos_1968_problem_2/: Conjectures that every large color-critical graph of chromatic number 3k-1 contains k vertex-disjoint odd circuits.

erdos_1969_problems_results_chromatic_graph_theory/: Survey of chromatic graph problems, covering critical graphs, girth versus chromatic number, and infinite chromatic numbers.

erdos_1974_general_properties_chromatic_numbers/: Proves every graph of uncountable chromatic number contains all sufficiently long odd cycles, and studies Taylor-type unboundedness of set systems.

erdos_1975_problems_results_3_chromatic_hypergraphs_related/: Shows simplicity or the clique property forces strong structure on 3-chromatic uniform hypergraphs, with degree, size and covering bounds.

erdos_1979_problems_results_graph_theory_combinatorial_analysis/: A problem collection in graph theory, opening with the conjecture that graphs whose subgraphs are nearly bipartite have bounded chromatic number.

erdos_1980_choosability_graphs/: Introduces list coloring, characterizes the 2-choosable graphs by their cores, and bounds the number of nodes of the smallest 2-colorable graph that is not k-choosable.

erdos_1982_almost_bipartite_large_chromatic_graphs/: Builds graphs of arbitrarily large chromatic number whose finite subgraphs are nearly bipartite, and limits this for uncountably chromatic graphs.

erdos_1985_problems_results_chromatic_numbers_finite_infinite_graphs/: Erdős's 1984 Kalamazoo problem paper on chromatic numbers of finite and infinite graphs; its p. 206 restates the El-Zahar-Erdős problem on two anticomplete subgraphs of large chromatic number.

erdos_1988_some_aspects_my_work_gabriel_dirac/: Surveys open problems on dense edge-critical graphs, recording Dirac's six-chromatic construction that gives E917's proposed constant 1/4 as a lower bound along orders congruent to 2 mod 4.

erdos_1995_problems_combinatorial_set_theory/: Erdos surveys nine sections of problems on ordinal partition relations, on graphs and triple systems of infinite or uncountable chromatic number and on colorings of the reals, some with prizes attached.

exoo_2019_6_chromatic_two_distance_graph_plane/: Constructs a finite plane graph with forbidden distances 1 and 2 that cannot be 5-colored, so the two-distance chromatic number is at least 6.

exoo_2019_bounds_smallest_k_chromatic_graphs_given/: Gives new computational lower and upper bounds on the smallest order of a k-chromatic graph of girth at least g for small k and g.

fleischner_stiebitz_1992_solution_colouring_problem_erdos/: Fleischner and Stiebitz's 1992 solution of Erdős's cycle-plus-triangles problem: Theorem 1.1, a 4-regular graph on 3n vertices decomposing into a Hamiltonian circuit and n vertex-disjoint triangles has chromatic number 3, proved through Alon and Tarsi's orientation criterion and the parity theorem 2.1 that such a digraph has e(D) ≡ 2 (mod 4) Eulerian arc sets.

gallai_1963_kritische_graphen_i/: Shows that in a k-critical graph the vertices of degree k minus 1 span a graph whose blocks are complete graphs and odd cycles, and constructs, for infinitely many n, 4-critical graphs on n vertices whose odd cycles are all longer than the square root of n.

gao_2021_strengthening_odd_cycles_graphs_given_chromatic/: Strengthens Gyarfas's theorem by showing a graph of chromatic number k+1 >= 3 contains cycles of floor(k/2) consecutive odd lengths.

gao_ma_2022_tight_bounds_towards_conjecture_gallai/: Proves the Abbott–Zhou bound of n-k+3 on the number of (k-1)-cliques in an n-vertex k-critical graph, which constrains E917 extremizers but gives no bound on their edge count.

gimbel_1986_three_extremal_problems_cochromatic_theory/: Determines the maximum cochromatic number of an n-vertex graph up to constants and disproves two conjectures on minimum size and genus.

gimbel_1997_coloring_graphs_fixed_genus_girth/: Bounds the largest chromatic number of a triangle-free graph on the orientable surface of genus g between constant multiples of g^(1/3)/log g and (g/log g)^(1/3), and shows that the largest cochromatic number of a graph on that surface is of order the square root of g over log g.

goncalves_2025_sphere_packings_euclidean_space_forbidden_distances/: Solves a constrained sphere packing problem in dimension 48, showing even unimodular extremal lattices are optimal, and unique among periodic packings, when an interval of short distances is forbidden.

gorskaya_2009_estimating_chromatic_numbers_euclidean_space_convex/: Recasts the linear-algebra lower bound for chromatic numbers of Euclidean space with k forbidden distances as convex minimization, solved for k up to 20.

graver_yackel_1968_graph_theoretic_results_associated_ramsey_theorem/: Graver and Yackel's 1968 study of the two-color Ramsey numbers as graphs with bounded clique and independence numbers: counting propositions bounding R(3,6) by 17 and R(3,7) by 22 in the paper's convention and two special constructions attaining both (18 and 23 in the usual one), cyclic graphs for the other lower bounds, welding for graphs with few edges, Corollary 4 adding three points per unit of independence number, and Proposition 9 with its Corollary, the upper bound R(x,y) at most B y^{x-1} log log y / log y for x at least 3.

gu_2026_twelve_critical_graphs/: Records two distinct Zenodo versions of Gu's unreviewed E917 preprint and separates its mathematical and Lean claims from verified credit.

gutner_1996_complexity_planar_graph_choosability/: Shows deciding 4-choosability of planar graphs and 3-choosability of triangle-free planar graphs is NP-hard, with small non-choosable examples.

gyarfas_1992_graphs_k_odd_cycle_lengths/: Proves that a 2-connected graph with exactly k odd cycle lengths, k at least 1, and minimum degree at least 2k plus 1 is the complete graph on 2k plus 2 vertices, so a graph with k odd cycle lengths has chromatic number at most 2k plus 2, with equality only when one of its blocks is that complete graph.

hanson_1996_choosability_bipartite_graphs/: Studies n(k), the least number of vertices of a bipartite graph that is not k-choosable, proving n(3) = 14 and the recursion n(k) at most k times n(k minus 2) plus 2 to the k, hence n(4) at most 40 and n(6) at most 304.

heckel_2021_non_concentration_chromatic_number_random_graph/: Proves the chromatic number of G(n,1/2) is not concentrated with high probability on fewer than n^(1/4-eps) consecutive values, for every fixed eps > 0, and the same for G(n,m) with m = floor(n^2/4).

heckel_2023_how_does_chromatic_number_random_graph/: Shows the chromatic number of a dense random graph has width at least n^(1/2-o(1)) for infinitely many n, nearly matching the known upper bound.

heckel_2024_difference_between_chromatic_cochromatic_number_random/: Shows that for about 95% of all n the chromatic minus cochromatic number of a random graph is at least n^{1-eps} with high probability.

heckel_2024_question_erdos_gimbel_cochromatic_number/: Proves the chromatic minus cochromatic number of a random graph is not whp bounded by n^{1/2-o(1)}, addressing but not settling a question of Erdos and Gimbel.

hindman_1981_conjecture_erdos_faber_lovasz_n_colorings/: Reduces the Erdos-Faber-Lovasz conjecture to a finite computation for families whose large sets span boundedly many points, verifying it up to ten such points.

janzer_2025_chromatic_number_regular_subgraphs/: Builds graphs of unbounded fractional chromatic number with no 4-regular subgraph, refuting the 1992 Erdos-Hajnal edge-disjoint-cycles problem.

jensen_2002_dense_critical_vertex_critical_graphs/: Constructs dense edge-critical graphs with prescribed minimum degree and dense vertex-critical circulants, some with no critical edge, and records Toft's quadratic lower bound that answers the first question of Problem 917.

jensen_toft_2001_25_pretty_graph_colouring_problems/: Lists 25 open graph colouring problems without proofs; Problems 3, 4, 5 and 25 pose the questions of E508, E19, E628 and E62 (the last for a wider class), and Problem 12, the minimum edge count of k-critical graphs, is context only for E917.

kang_2021_proof_erdos_faber_lovasz_conjecture/: Proves that every linear hypergraph on a large number of vertices has chromatic index at most that number, with stability versions.

kang_2024_solution_problem_erdos_chromatic_index_hypergraphs/: Proves every n-vertex hypergraph with degree at most (1-o(1))tn and codegree at most t has chromatic index at most tn, answering a 1977 Erdos question for t >= 2.

lambiehanson_2020_growth_rate_chromatic_numbers_finite_subgraphs/: Proves in ZFC that for every function f there is an uncountably chromatic graph whose small subgraphs all have small chromatic number.

li_2026_erdoshajnal_high_girth_subgraph_conjecture_holds/: Proves the Erdős-Hajnal high-girth subgraph conjecture for graphs whose edge count is bounded by a fixed power of their chromatic number.

liu_2020_solution_erdos_hajnal_s_odd_cycle/: Proves an asymptotically sharp odd-cycle harmonic bound and long even-cycle intervals, solving the odd-cycle problem and forcing powers of two.

liu_2026_remarks_theorem_erdos_szemeredi/: Proves the Erdős-Szemerédi theorem on unbalanced two-edge-colorings with all parameter dependencies made explicit.

luo_2023_maximum_number_edges_critical_graphs/: Improves the 35-year-old upper bound on the edge count of k-critical graphs, gaining a quadratic saving and giving f_4(n) < 0.164 n^2 for large n.

martinsson_2025_vertex_critical_graphs_far_edge_criticality/: For every fixed r and all large k there is a k-chromatic vertex-critical graph that stays k-chromatic after deleting any r of its edges.

mohar_2015_dichromatic_number_fractional_chromatic_number/: Proves a fractional version of the Erdos-Neumann-Lara conjecture, bounding fractional dichromatic number below in terms of fractional chromatic number.

naslund_2023_chromatic_number_r_n_multiple_forbidden/: Improves the exponential lower bound for the m-distance chromatic number of n-dimensional Euclidean space, with an explicit constant near 0.79983.

nastase_et_al_2010_note_robust_critical_graphs_large_odd_girth/: Constructs arbitrarily large edge-critical graphs of large odd girth that need quadratically many edge deletions to drop two colors, giving E917 a quadratic lower bound along a sequence of orders.

parts_2020_small_6_chromatic_two_distance_graph/: Gives a 31-vertex two-distance graph proving the plane needs at least six colors when the forbidden distances are 1 and the golden ratio.

parts_2023_more_certainty_coloring_plane_forbidden_distance/: Enlarges the known intervals of forbidden distances for which the chromatic number of the plane is known exactly, and adds new ones.

pegden_2011_critical_graphs_without_triangles_optimum_density_construction/: Constructs triangle-free k-critical graphs of density 1/16, 4/31 and 1/4 for k=4, 5 and at least 6, which by themselves give a quadratic lower bound for E917's f_k(n) for every k and reach the proposed constant 1/4 from below for k=6,7,8.

petkov_2026_full_sequence_chromatic_cochromatic_gap/: Proves an explicit n/(log n)^3 lower bound for the gap along all integers, with public kernel verification reported for the uniform theorem.

radhakrishnan_2000_improved_bounds_algorithms_hypergraph_coloring/: Proves that for large n every n-uniform hypergraph with at most 0.7 sqrt(n/ln n) 2^n edges is two-colorable, with fast algorithms finding such a coloring.

reiher_2024_graphs_large_girth/: A survey of graphs of large girth, covering Moore-bound extremal problems and Ramsey-theoretic constructions including the girth Ramsey theorem.

sachs_1993_elementary_proof_cycle_plus_triangles_theorem/: Sachs proves that the number of distinct color-class partitions is odd, giving the cycle-plus-triangles theorem as a direct corollary.

scott_2008_concentration_chromatic_number_random_graphs/: Gives a proof that for fixed p the chromatic number of G(n,p) is concentrated in an interval of length omega(n) sqrt(n)/log n.

scott_2018_survey_chi_boundedness/: Surveys the state of chi-boundedness, collecting the Gyarfas conjectures of the early 1980s and the recent progress on them.

shelah_1990_incompactness_chromatic_numbers_graphs/: Builds graphs of large chromatic number whose smaller subgraphs have small chromatic number, by forcing under GCH and in the constructible universe, and proves in that universe and in a model from a supercompact cardinal that certain chromatic numbers are attained by subgraphs.

shelah_2012_incompactness_chromatic_number_graphs/: Builds, from a non-reflecting stationary set, a graph of chromatic number above kappa all of whose smaller subgraphs are kappa-colorable.

simonovits_1972_colour_critical_graphs/: Bounds how many independent vertices of valence at least m a k-critical graph can have and builds 4-critical graphs of large minimum degree.

skottova_2025_critical_edge_sets_vertex_critical_graphs/: Resolves Erdos's problem on critical edge sets for all k >= 5, proving f_k(n) grows at least like n^(1/3) there and at most like n/(log n)^c for k >= 4.

steiner_2024_difference_between_chromatic_cochromatic_number/: Disproves the Erdos-Gimbel-Straight conjecture on chromatic minus cochromatic number and gives partial evidence for their random-graph question.

This folder holds sources whose primary subject is Graph Coloring.

Sources with other primary subjects

Explicit links to this subject's problems support these cross-references.

Linked from (88)

Graph