Extremal and Structural Graph Theory

../

adamczewski_2026_erdos548/: Presents the permutation-counting proof of the Erdős–Sós tree edge bound; two-color and multicolor Ramsey corollaries are derived here.

adamczewski_2026_erdos571/: Reconstructs the public 2026 proof of every rational bipartite Turán exponent, with its preliminary exposition, pinned Lean source and provenance.

ajtai_1981_longest_path_random_graph/: Proves that a random graph with (1+epsilon)n/2 edges, or a random directed graph with (1+epsilon)n edges, almost surely contains a path of length linear in n, settling a conjecture of Erdos.

ajtai_1981_turan_s_theorem_sparse_graphs/: Shows that forbidding a fixed clique improves the Turán independence bound for graphs of given average degree, and states the conjecture that the improvement is the full log t factor known for triangle-free graphs.

alavi_1987_vertex_independence_sequence_graph_is_not/: Proves every ordering of the counts of independent vertex sets by size is realized by some graph, so the sequence is unconstrained.

allen_2021_tree_packing_conjecture_trees_almost_linear/: Proves the tree packing conjecture for all large n when every tree has maximum degree at most cn/log n.

almasi_2023_ramsey_turnaround_numbers/: Master's thesis bounding Ramsey turnaround numbers, in which Painter seeks a monochromatic graph while Builder forbids colors, with lower bounds for complete graphs from matchings, projective-plane balanced colorings and random colorings, and examples where online strategies beat offline ones.

alon_1984_every_regular_graph_plus_edge_contains/: The two-page note of Alon, Friedland and Kalai proving by Chevalley's theorem that a 4-regular loopless multigraph with one added edge contains a 3-regular subgraph, with a remark attesting Tashkinov's proof of the Berge-Sauer conjecture.

alon_1985_maximum_number_disjoint_pairs_family_subsets/: Proves Erdős--Stone type bounds for the numbers of disjoint and of comparable pairs in a family of 2^((1/(k+1)+delta)n) subsets of an n-set, with generalizations and a construction on comparable pairs.

alon_1991_ramsey_graphs_contain_many_distinct_induced/: Ramsey graphs contain many distinct induced subgraphs.

alon_1996_bipartite_subgraphs/: Settles an Erdos problem by showing graphs with 2m^2 edges have bipartite subgraphs with m^2+m/2+c sqrt(m) edges, and sharpens the triangle-free bound.

alon_1996_independence_numbers_locally_sparse_graphs_ramsey/: Strengthens the Ajtai–Komlós–Szemerédi independence bound to graphs whose vertex neighborhoods are r-colorable, and settles Erdős's 1979 Ramsey-type question: a graph on n vertices with independence number below ⌊√n⌋ has a ⌊√n⌋-set spanning order √n log n edges, which is tight.

alon_1998_bipartite_subgraphs_integer_weighted_graphs/: Proves an exact recurrence for maximum cuts in integer-weighted graphs near a triangular total weight and derives exact values for many simple graphs.

alon_2000_decreasing_diameter_bounded_degree_graphs/: Gives exact and asymptotic bounds for unrestricted edge additions that reduce graph diameter, including sharp bounded-degree results.

alon_2001_ramsey_type_theorems_forbidden_subgraphs/: Shows the Erdos-Hajnal property is preserved when vertices of a graph are replaced by graphs, and proves the Erdos-Hajnal conjecture equivalent to its version for tournaments.

alon_2003_turan_numbers_bipartite_graphs_related_ramsey/: Bounds Turan numbers of degenerate bipartite graphs and proves the Erdos exponential Ramsey conjecture for bipartite graphs with m edges.

alon_2006_extremal_hypergraph_problem_brown_erdos_sos/: Settles the three-edge case of the Brown-Erdős-Sós problem for every uniformity and every exponent, extending the Ruzsa-Szemerédi and Erdős-Frankl-Rödl theorems.

alon_2007_graphs_subgraphs_having_large_independence_numbers/: Bounds the independence number forced by every small induced subgraph having a large independent set, answering questions of Erdos and Hajnal.

alon_2007_large_nearly_regular_induced_subgraphs/: Bounds the largest nearly regular induced subgraph forced in every n-vertex graph, including a new upper bound for the regular case.

alon_2008_problems_results_extremal_combinatorics/: Alon's second collection of extremal problems and results, opening with the disproof of the Erdős-Simonovits question on almost-regular subgraphs of graphs with n log n edges by a random bipartite construction.

alon_2015_bipartite_decomposition_random_graphs/: Disproves the Erdos conjecture that the random graph needs exactly n minus its independence number bicliques to decompose its edges.

alon_2015_comparable_pairs_families_sets/: Bounds how many comparable pairs a family of m subsets of an n-set can have, resolving a conjecture of Alon and Frankl.

alon_2017_more_bipartite_decomposition_random_graphs/: Strengthens the disproof of the Erdos biclique decomposition conjecture, showing the random graph needs at most n minus (1+c) times its independence number.

alon_2021_large_cliques_independent_sets_all_over/: Constructs graphs in which every sufficiently large vertex subset contains both a clique and an independent set of logarithmic size.

alon_2026_problems_results_extremal_combinatorics_v/: Proves that every sufficiently low-degree triangle-free graph can be completed to diameter two after adding a subquadratic number of edges.

andersen_1992_strong_chromatic_index_cubic_graph_is_at_most_10/: Andersen's 1992 proof that every graph of maximum degree at most three, multiple edges allowed, has a strong edge-coloring with at most ten colors, by a greedy algorithm linear in the number of vertices; the case of maximum degree three of the Erdős–Nešetřil strong chromatic index conjecture, obtained independently of Horák, He and Trotter, with a seven-vertex graph of strong chromatic index exactly ten.

andrasfai_et_al_1974_connection_between_chromatic_number_maximal_clique_minimal_degree_graph/: Proves the sharp minimum-degree threshold above which a K_r-free graph has chromatic number below r.

anto_2023_gallai_s_path_decomposition_2_degenerate/: Shows the edges of any connected 2-degenerate graph on n vertices split into at most n/2 paths unless the graph is a triangle.

baber_2012_turan_densities_hypercubes/: Extends the semidefinite flag algebra method to hypercubes, lowering the upper bound for the edge Turan density of a 4-cycle-free subcube to 0.60318.

bacso_et_al_2004_coloring_maximal_cliques_graphs/: Proves that claw-free perfect graphs are 2-clique-colorable and almost all perfect graphs 3-clique-colorable, which yields only constant-fraction clique-transversal bounds for E611.

bacso_tuza_2009_clique_transversal_sets_weak_2_colorings_graphs_small_maximum_degree/: Bounds clique transversals of connected subcubic graphs by 19n/30 plus a constant and weakly 2-colors connected claw-free graphs of maximum degree at most four except odd holes, too degree-restricted to settle E611.

balogh_2013_ramsey_turan_numbers_graphs_hypergraphs/: Shows the K_t-independence Ramsey-Turan number of K_{t+2} is quadratic, answering a question of Erdos, Hajnal, Simonovits, Sos and Szemeredi.

balogh_2014_upper_bounds_cycle_free_subgraphs_hypercube/: Adapts flag algebras to the hypercube, lowering the upper bounds for 4-cycle-free and 6-cycle-free subgraph densities to 0.6068 and 0.3755.

balogh_2021_max_cuts_triangle_free_graphs/: For sufficiently large order, bounds triangle-free bipartization by n^2/23.5 and proves n^2/25 in two specified edge-density ranges.

balogh_2025_packing_edge_disjoint_cliques_graphs/: Proves Győri's conjecture that an n-vertex graph with t_{r−1}(n) + k edges has at least (2 − o(1))k/r edge-disjoint r-cliques, through a fractional packing theorem; its concluding remarks restate Győri's exact ranges for edge-disjoint triangles and show that K_4-freeness matters beyond k = 17n²/169.

bartfai_1960_solution_problem_posed_erdos/: Shows every loopless graph on 2n+1 vertices with at least 3n+1 edges contains a simple closed circuit of even length, and that 3n edges do not suffice.

basit_galvin_2020_independent_set_sequence_tree/: Proves that the independent set sequence of every graph, so of every forest, decreases over a final segment and that of every tree increases over an initial one, and that a.a.s. the sequence of a uniform random labelled tree increases up to 0.280n and decreases from 0.347n.

bencs_2017_trees_real_rooted_independence_polynomial/: Shows that the stable-path tree of a claw-free graph has a real-rooted independence polynomial, and so proves real-rootedness, hence unimodality, for centipedes, caterpillars and Fibonacci trees, the last with an index shift in the proof.

bennett_2022_erdos_gyarfas_function_so_gyarfas_was/: Constructs edge-colorings of the complete graph in which every four vertices span at least five colors using (5/6)n + o(n) colors, which is asymptotically the fewest possible.

benson_1966_minimal_regular_graphs_girths_eight_twelve/: Constructs regular graphs of degree q+1 attaining Tutte's order bound at girth eight and girth twelve using incidence in quadrics.

bermond_1983_graphs_interconnection_networks_diameter_vulnerability/: Surveys diameter and connectivity of interconnection networks: degree-diameter graphs, disjoint paths, diameter vulnerability and hypergraphs.

blanche_2021_gallai_s_path_decomposition_planar_graphs/: Proves Gallai's conjecture for planar graphs: every connected planar graph on n vertices decomposes into ceil(n/2) paths.

blumenthal_2021_sharp_bounds_decomposing_graphs_edges_triangles/: Determines, for all large n, the exact maximum over n-vertex graphs of the cheapest decomposition of the edges into single edges and triangles, with the complete graph and the balanced complete bipartite graph the only extremal graphs, and does the same for every triangle cost alpha; its proof of Lemma 11 quotes, and its Section 5 reports, Győri's 1988 theorem that t_2(n) + k edges on n vertices, with k = o(n²), force k − O(k²/n²) edge-disjoint triangles.

bohman_2015_random_triangle_removal/: Proves the random greedy triangle removal process ends with n^(3/2+o(1)) edges, confirming the exponent conjectured by Bollobas and Erdos.

bollobas_1962_grafelmeleti_szelsoertekekre_vonatkozo_problemakrol_extremal_problems/: Hungarian paper on the least edge count forcing two vertices joined by three independent paths and on topological complete subgraphs, proving Pósa's conjecture that the same count forces a cycle with an outside vertex joined to two of its vertices.

bollobas_1975_complete_subgraphs_chromatic_graphs/: Studies how large a minimum degree forces a complete subgraph in an r-partite graph with equal parts, with between t³ and 4t³ forced triangles at minimum degree n + t for three parts, lower bounds on the thresholds c_r for r at least 4, and the conjecture that c_r minus r plus 2 tends to one half.

bollobas_1976_ramsey_turan_type_problem/: Proves the Ramsey-Turan density for K_4 is exactly one eighth, showing Szemeredi's upper bound cannot be improved.

bollobas_1983_some_remarks_packing_trees/: Bollobás's 1983 note on the Gyárfás–Lehel tree packing conjecture: if 3 ≤ s < n/√2 and T_i is a tree of order i, then any packing of the trees T_{k+1}, ..., T_s into the complete graph on n vertices extends by T_k, so T_2, ..., T_s pack greedily in descending order of size; with the remark that the Erdős–Sós conjecture would raise the bound to (√3/2) n.

bollobas_2002_better_bounds_max_cut/: Bollobás and Scott on the least largest cut of a graph with m edges: exact values and extremal graphs at m = C(n,2) + C(k,2), the weighted recurrence that fixes the simple-graph function within a constant, exact values for greedy triangular decompositions, linear-time algorithms, and k-cut and directed analogues.

bollobas_2005_sum_degrees_cliques/: Proves the Bollobás–Erdős conjecture that a graph with at least the Turán number of edges has an r-clique whose degree sum is at least 2rm/n, with strict inequality for non-regular graphs, and shows the bound is stable just below the Turán number.

bollobas_hind_1991_graphs_without_large_triangle_free_subgraphs/: Bollobás and Hind's 1991 bounds on the Erdős–Rogers function f_{r,s}(n), the largest K^r-free induced subgraph forced in every K^s-free graph on n vertices: (2n)^{1/2} ≤ f_{3,4}(n) ≤ n^{7/10+ε} and, for 3 ≤ r < s, n^{1/(s−r+1)} ≤ f_{r,s}(n) ≤ n^{(s−3)/(s−2)+2/(s+1)(s−2)+ε}, the upper bounds by random hypergraphs whose graphs are made clique-free by deleting hyperedges.

bollobas_thomason_1981_dense_neighbourhoods_turan_s_theorem/: Bollobás and Thomason's 1981 note proving Erdős's extension of Turán's theorem: a graph of order n with at least t_r(n) edges is either the Turán graph T_r(n) or has a vertex x of degree d > n(1 − 1/r − 1/(1 + √r)) whose neighborhood spans at least t_{r−1}(d) + 1 edges, by a triangle count against the degree sequence.

bollobas_thomason_1998_proof_conjecture_mader_erdos_hajnal_topological_complete_subgraphs/: Bollobás and Thomason's 1998 proof of the conjecture of Mader and of Erdős and Hajnal that a constant times p squared times the order in edges forces a topological complete subgraph of order p: Theorem 4, every graph G of size 256 p^2 |G| contains a topological complete subgraph of order p, through a linkage theorem for highly connected graphs with a dense minor (Theorem 1) and a dense-minor lemma (Lemma 3).

bonamy_2019_gallai_s_path_decomposition_conjecture_graphs/: Proves Gallai's conjecture that a connected graph on n vertices decomposes into at most ceil(n/2) paths for all graphs of maximum degree at most five.

bonamy_2022_colouring_graphs_sparse_neighbourhoods_bounds_applications/: Improves coloring bounds for sparse-neighborhood graphs, proving for large maximum degree the epsilon-version of Reed's conjecture with epsilon = 1/26 and a strong chromatic index bound 1.835 Delta^2.

bondy_1971_large_cycles_graphs/: Bondy's 1971 paper proving Erdős's Oxford conjecture that a graph of order n with at least (n^2 − 5n + 14)/2 edges has a cycle of length n − 1, posing the general conjecture f(r, n) = g(r, n) for r ≤ (n − 1)/2, where f(r, n) is the least size forcing a cycle of length n − r + 1 and g(r, n) = (n^2 − (2r + 1)n + 2r^2 + 2r + 2)/2, and stating that the conjecture holds for all n ≥ (r^2 + 5r + 4)/2; also bounds on the circumference of a block and on the size of a graph of circumference c.

bondy_1971_pancyclic_graphs_i/: Bondy's 1971 paper proving that a Hamiltonian graph on n vertices with at least n^2/4 edges is pancyclic or the balanced complete bipartite graph, with the corollary that Ore's Hamiltonicity condition gives the same alternative; its conclusion poses the minimum number of edges p(n) of a pancyclic graph of order n and states, with "we can prove that" and no proof, the bounds n − 1 + log_2(n − 1) ≤ p(n) ≤ n + log_2 n + H(n) + O(1).

bondy_1974_cycles_even_length_graphs/: Proves that a graph on n vertices with at least 100k n^(1+1/k) edges contains a cycle of length 2l for every integer l between k and k n^(1/k).

bondy_1983_large_dense_neighbourhoods_turan_s_theorem/: Bondy's 1983 note proving that in a graph on n vertices with more than t_r(n) edges, the Turán number for complete graphs on r + 1 vertices, the neighborhood of any vertex of maximum degree m induces more than t_{r-1}(m) edges; it restates the Bollobás–Thomason theorem on graphs with at least t_r(n) edges with their degree bound, gives examples with exactly t_r(n) edges where the maximum-degree vertex fails, and is corrected by a 1983 erratum.

boros_2025_conformality_minimal_transversals_maximal_cliques/: A 2025 preprint of Boros, Gurvich, Milanič, Tikhanovsky and Uno on graphs whose minimal clique transversals form the maximal cliques of a graph ("clique dually conformal" graphs): characterizations within triangle-free and split graphs with polynomial recognition, and closure under substitution; structural literature on clique transversals adjacent to Problem 151, not bearing on its inequality.

bradac_2024_question_erdos_nesetril_about_minimal_cuts/: Shows a graph on n vertices has at most about 1.8899 to the n inclusion-wise minimal vertex cuts, so the growth rate is below two.

bradac_2024_unique_subgraphs_are_rare/: Proves that no graph on n vertices has a constant proportion of all n-vertex graphs as unique subgraphs, answering Erdos's question in the negative, as he expected.

brouwer_1975_note_number_unique_subgraphs_graph_j/: Determines the maximum number of unique subgraphs of an n-vertex graph, with base-two logarithm n squared over two minus n log n plus O(n).

brouwer_1993_highly_symmetric_subgraphs_hypercubes/: Settles a problem of Erdős by showing four colors suffice to color the n-cube's edges with no monochromatic quadrangle or hexagon.

brown_1966_graphs_that_do_not_contain_thomsen/: Constructs graphs on p cubed vertices with no complete bipartite three by three subgraph, proving the conjectured n to the five thirds lower bound.

brown_1973_extremal_problems_graphs/: Proves a probabilistic lower bound of order n to the power (rs-k)/(s-1) for extremal r-uniform hypergraphs avoiding k vertices spanning s edges.

bruhn_2018_stronger_bound_strong_chromatic_index/: Proves the strong chromatic index is at most 1.93 times the square of the maximum degree for graphs of large maximum degree.

bucic_2019_universal_unavoidable_graphs/: Determines the maximum size of an unavoidable graph in the last open dense range, answering a 1983 question of Chung and Erdos.

bucic_2020_large_independent_sets_local_considerations/: Improves lower bounds on the independence number of graphs whose every m vertices contain an independent set of size r, in particular the exponent 5/12 minus o(1) when every seven vertices contain an independent triple.

bucic_2022_towards_erdos_gallai_cycle_decomposition_conjecture/: Shows every graph on n vertices decomposes into O(n log-star n) cycles and edges, improving the previous n log log n bound.

bucic_2023_induced_subgraph_density_i_loglog_step/: Gives the first general improvement on the Erdos-Hajnal bound, finding a clique or stable set of size exponential in root log times root loglog.

bujtas_2025_covering_edges_graph_triangles/: Bounds the least number of edges and triangles covering all edges of a graph in terms of the edge count, the triangle-independence number and the triangle packing number, proves Nordhaus-Gaddum-type bounds for these invariants, and quotes the Norin-Sun inequality as its Theorem 2.

bukh_2018_rational_exponents_extremal_graph_theory/: Constructs for every rational r between 1 and 2 a finite family of graphs whose extremal number grows like n to the power r.

caccetta_haggkvist_1979_diameter_critical_graphs/: Caccetta and Häggkvist's 1979 paper on diameter-critical graphs: the Simon–Murty conjecture that a diameter 2-critical graph on v vertices has at most [v^2/4] edges, printed as Conjecture 1 with its equality clause; Theorem 1, that such a graph has fewer than ((1+√5)/12) v^2 < 0.27 v^2 edges; Theorem 2, average edge degree at most 6v/5; and a conjectured extremal number for diameter k-critical graphs with k ≥ 3.

cambie_2022_maximizing_line_subgraphs_diameter_at_most_t/: Bounds the largest edge count of a bounded-degree graph whose line graph has diameter at most t, an edge version of the degree-diameter problem.

cambie_2025_edge_colouring_games_erdos_bensmail_mc/: Advances three competitive edge-coloring games, resolving the biased maximum-degree and vertex-capturing games and the biased clique game with bias three.

cambie_2025_sharp_results_erdos_pach_pollack_tuza/: Determines the sharp diameter-to-order ratio for K4-free graphs of small minimum degree and disproves a conjecture of Erdős and coauthors.

camesvanbatenburg_2020_strong_cliques_forbidden_cycles/: Bounds the strong clique number of graphs with a forbidden cycle length, giving evidence for the Erdos-Nesetril strong chromatic index conjecture.

carmesin_2023_characterising_graphs_no_subdivision_wheel_bounded_diameter/: Carmesin's 2023 paper characterizing the graphs with no r-bounded subdivision of a wheel by graph-decompositions of locality r and width at most two; held for its Related results paragraph, which restates Thomassen's 1974 theorem that 2n−2 edges force a cycle with a vertex adjacent to three of its vertices.

chaffee_2016_dimension_4_dimension_5_graphs_minimum/: Chaffee and Noble's short proof that a graph of dimension 4 has at least nine edges, with K_{3,3} the only nine-edge example, and the extension to dimension 5 (fifteen edges; K_6 and K_{1,3,3}).

chahua_2025_tuza_s_conjecture_dense_graphs/: Chahua and Gutiérrez's three results on Tuza's conjecture for dense graphs: the conjecture for split graphs of minimum degree at least 3n/5, the bound τ ≤ n²/(3(4m − n²)) ν for tripartite graphs with m > n²/4 edges (so τ < 28ν/15 above 33n²/112 edges), and the tight τ ≤ 3ν/2 for complete 4-partite graphs on at least five vertices; retained as the 2024 arXiv preprint of a 2025 Discrete Applied Mathematics paper.

chakraborti_2024_edge_disjoint_cycles_same_vertex_set/: Shows any n-vertex graph with n times a polylogarithmic factor many edges contains k edge-disjoint cycles on the same vertex set, for every fixed k.

chakraborti_2024_regular_subgraphs_at_every_density/: Settles the Erdos-Sauer problem up to an absolute constant, showing average degree C r^2 log log n forces an r-regular subgraph.

chen_1994_clique_partitions_split_graphs/: Shows that the edges of every split graph on n vertices can be partitioned into at most (3/16)n^2 + O(n) cliques, that n^2/6 + O(n) suffice for the difference of two cliques, and conjectures that n^2/6 + n/6 always suffice.

chen_1997_result_c4_star_ramsey_numbers/: Chen's 1997 note proving that the C_4-star Ramsey number grows by at most two from one star to the next, r(C_4, K_{1,n+1}) <= r(C_4, K_{1,n}) + 2 for all positive integers n, answering a question of Burr, Erdős, Faudree, Rousseau and Schelp.

chen_2025_problem_erdos_hajnal_paths_equal_degree/: Proves that for n at least 600 every graph on 2n+1 vertices with at least n^2+n edges other than the complete bipartite graph with parts n and n+1 has two equal-degree vertices joined by a path of length three.

chu_2026_gallai_s_conjecture_path_number_odd_semi_cliques/: Chu, Fan and Zhou's 2026 paper on Gallai's path conjecture: Theorem 1.3, a graph on n vertices whose even-degree vertices induce a complete graph K_m with m at most 15 decomposes into at most floor(n/2) + 1 edge-disjoint paths, hence ceil(n/2) when n is odd; Theorem 1.4, the star form behind it, floor(n/2) + ceil(|E(S)|/14) paths; Theorem 1.5, (4n+6)/7 paths for a graph with a universal vertex; and Theorem 1.7, (4n+6)/7 paths for every semi-clique, a graph that needs at least ceil(n/2) paths.

chudnovsky_2008_erdos_hajnal_conjecture_bull_free/: Proves that every bull-free graph on n vertices has a clique or a stable set of size at least n^(1/4), the Erdős-Hajnal conjecture for the bull.

chudnovsky_2023_erdos_hajnal_graphs_no_5_hole/: Proves the Erdős–Hajnal conjecture for the five-cycle, and the Erdős–Hajnal property for several pairs and families of excluded graphs built from cycles and forests.

chung_1979_product_point_line_covering_numbers_graph/: Settles two conjectures of Harary and Kabell on the product of the point covering number and the line covering number of a graph on n points, proving the minimum n-1 with equality only for stars and the maximum (n^2-1)/2 for n odd, attained only by K_n, and (n^2-4)/2 for n even, attained only by K_4 when n = 4 and otherwise by two disjoint odd cliques, and extends the bounds to r-uniform hypergraphs; the site's source key for Problem 581, which it does not mention.

chung_1990_maximum_number_edges_2k2_free_graphs_bounded_degree/: Chung, Gyárfás, Tuza and Trotter's 1990 theorem that a connected graph with no induced pair of independent edges and maximum degree at most D has at most 5D²/4 edges for even D and (5D² − 2D + 1)/4 for odd D, with the blown-up five-cycle as the unique extremal graph; the t = 2 case of the Erdős–Nešetřil edge-distance function and the strong-clique case of their strong edge-coloring conjecture.

chung_1997_open_problems_paul_erdos_graph_theory/: Chung's 1997 survey of Erdos's open problems in graph theory, each with its sources and references and, where Erdos offered one, its prize; Problem 75 is the odd-cycle decomposition question of #609 and Problem 73 the unavoidable cycle lengths question.

codex_terpstra_2026_fixed_r10_r11_erdos_617/: Gives computer-assisted proofs of the fixed ten- and eleven-color cases of Problem 617 through inherited density bounds and clique-packing recurrences, with two clean-room audits reported and no proof-assistant certificate.

conlon_2014_cycle_packing/: Shows every graph on n vertices decomposes into O(n log log n) cycles and edges, the first progress on the Erdos-Gallai conjecture.

conlon_2014_large_subgraphs_without_complete_bipartite_graphs/: Determines up to constants the largest complete-bipartite-free subgraph guaranteed in any graph with m edges, and the hypergraph analog.

conlon_2021_extremal_number_subdivisions/: Proves that any C4-free bipartite graph with maximum degree two on one side has extremal number O(n^{3/2-delta}), answering a 1988 question of Erdos.

conlon_2021_more_extremal_number_subdivisions/: Determines extremal numbers of several subdivided bipartite graphs and produces infinitely many new realizable rational Turan exponents.

conlon_2021_random_multilinear_maps_erdos_box_problem/: Lower bounds for the Erdős box problem from random multilinear maps, improving the deletion bound for every uniformity and the Gunderson-Rödl-Sidorenko bound for every uniformity that is not a power of two.

conlon_2022_rational_exponents_near_two/: Proves the Erdos-Simonovits rational exponents conjecture for every rational of the form 2 - a/b with b large in terms of a.

conlon_2023_ramsey_numbers_zarankiewicz_problem/: Links off-diagonal Ramsey numbers to a matrix version of the Zarankiewicz problem, giving new lower bounds for the Ramsey numbers of the 5-cycle and 7-cycle.

cooper_et_al_2016_optimal_size_clique_transversals_chordal_graphs/: Proves the sharp bound 2(n-1)/7 on clique transversals of n-vertex chordal graphs in which every edge lies in a 4-clique, a constant-fraction bound that does not give E611's sublinear estimate.

csaba_2025_ramsey_turan_problem_4_cliques/: A regularity-free proof that an n-vertex graph with independence number αn, α at most an absolute constant, and more than (n² + n)/8 + (α − α²)n²/2 edges contains a K_4, with single-exponential constants; refines the Lüders–Reiher bound above the Bollobás–Erdős density n²/8.

csikvari_nagy_2014_density_turan_problem/: Develops density criteria for transversal copies in graph blow-ups, including an efficient tree test, degree bounds, and star-decomposition extremal constructions.

czabarka_2009_diameter_4_colourable_graphs/: Czabarka, Dankelmann and Székely's 2009 proof that every connected 4-colorable graph of order n and minimum degree δ ≥ 1 has diameter at most 5n/(2δ) − 1, which the paper calls a first step toward the 1989 Erdős–Pach–Pollack–Tuza diameter conjecture: its K_5-free case under the stronger hypothesis of 4-colorability, tight up to the additive constant by the 1989 construction.

czabarka_2021_counterexamples_conjecture_erdos_pach_pollack_tuza/: Disproves the Erdos-Pach-Pollack-Tuza diameter conjecture for clique-free graphs and proves replacement bounds for k-colorable graphs.

czabarka_2023_maximum_diameter_3_4_colorable_graphs/: Proves that every connected k-colorable graph of order n and minimum degree at least d >= 1 has diameter at most (3 - 2/k)n/d - 1 for k = 3 and 4.

davey_2026_strong_edge_colouring_local_flag_algebras/: A July 2026 preprint of Davey, Hurley, de Joannis de Verclos, Kang and Volec claiming the strong chromatic index bounds 1.73 Δ² for all graphs, 1.6255 Δ² for bipartite graphs and 1.6633 Δ_A Δ_B for asymmetric bipartite graphs, all for large degree, by local flag algebras with computer certificates; unrefereed, with a declared use of an agentic AI system for its Lean verification, counterexample searches, the proofs of Theorem 1.4 and Proposition 8.1, and drafting its exposition.

devos_rollova_samal_2019_counting_flows_signed_graphs/: Extends Tutte's group-order polynomial for nowhere-zero flows to signed graphs by adding the 2-rank of the abelian group as the necessary parameter.

dibraccio_2026_leaf_to_leaf_paths_cycles_degree_critical_graphs/: Shows every degree 3-critical graph on n vertices has Ω(log n) distinct cycle lengths and settles two conjectures of Narins, Pokrovskiy and Szabó on leaf-to-leaf path lengths in 1–3 trees; its Problem F restates their open question on even cycle lengths 4, 6, ..., 2C(n).

didin_2026_asymptotic_solution_1_2_biased_erdos/: Proves that the two-edge player wins the (1:2)-biased clique-building game on the complete graph for all sufficiently large vertex counts.

dirac_1960_in_abstrakten_graphen_vorhandene_vollstandige_4_graphen_und_ihre_unterteilungen/: Dirac's 1960 paper on complete 4-graphs and their subdivisions in abstract graphs: Satz 6, every finite graph on N at least 4 vertices with at least 2N − 2 edges contains a K_4 or a subdivision of one, best possible by the 2N − 3 edge examples of its Figures 3--5; with degree conditions (Sätze 4 and 5) forcing such a subgraph, and counts of the K_4 subdivisions through given vertices, edges and cycles of 3-connected and n-connected graphs.

dirac_1963_extensions_turan_s_theorem_graphs/: Dirac's 1963 extensions of Turán's theorem: a graph on n vertices with at least d_k(n) + α edges (α ≤ 1) contains, for every n' from k to n − 1, a subgraph on n' vertices with at least d_k(n') + α edges; so more than d_k(n) edges force K_{k+p} minus p edges for n ≥ k + p ≥ 2p + 2, and at exactly d_k(n) edges only the Turán graph avoids them if n ≥ k + p + 1 and p ≤ k − 3. At k = 3 the first theorem is the Dirac half of the statement that [n²/4] + 1 edges force, for every n' from 3 to n, an n'-vertex subgraph with [n'²/4] + 1 edges.

diskin_samotij_2025_isoperimetry_product_graphs/: Establishes a tensorized edge-isoperimetric inequality for Cartesian products through convex minorants of coordinate isoperimetric profiles, with explicit Hamming, grid, torus and regular-product bounds, and answers two questions of Diskin, Erde, Kang and Krivelevich on powers of regular graphs.

draganic_2024_cycles_many_chords/: Shows that n log to the eighth power n edges force a cycle with at least as many chords as vertices, far improving the old n to the three halves bound.

draganic_2025_cyclic_subsets_regular_dirac_graphs/: Solves the Erdős–Faudree cyclic-subset question and identifies an exact extremal family, with reconstruction limits recorded for the exact proof.

draganic_girao_2026_cycles_almost_linearly_many_chords/: Proves that sufficiently large constant minimum degree forces a cycle with almost linearly many chords relative to its length, a count that stays below the one-chord-per-vertex threshold of E642.

duke_1982_subgraphs_which_each_pair_edges_lies/: Shows every dense graph contains a subgraph with quadratically many edges in which every two edges lie on a common cycle of length four or six.

duke_1984_more_results_subgraphs_many_short_cycles/: Determines up to constants the largest subgraph that every graph with n vertices and n^{2-e} edges contains with every two edges on a common cycle of length at most 6 (or at most 12).

duke_1992_cycle_connected_graphs/: Duke, Erdős and Rödl's 1992 paper on subgraphs and edge sets in which every two edges lie on a 4-cycle: the largest such subgraph guaranteed in a graph with a constant fraction of all edges has only linearly many edges (Theorem 1), and edge sets shrink only after about n^{3/2} deletions (Theorems 5--10). The introduction states the authors' fixed-density result for cycles of length at most 8, and the concluding remarks pose the sparse question Fox and Sudakov later settled for beta < 1/5.

dvorak_et_al_2025_lollipops_dense_cycles_chords/: Refines Gupta, Kahn and Robertson's theorem that minimum degree k forces a cycle with at least (k+1)(k-2)/2 chords to give dense cyclic minors; for E642 the chord bound yields only a coarse O(n^{3/2}) edge bound weaker than the known one.

dyson_2026_ramsey_numbers_regular_induced_subgraphs/: Proves a clean quadratic lower bound for forcing a regular induced subgraph, computes the exact values for order 5 and lower bounds for orders 6 and 7.

edmonds_1965_maximum_matching_polyhedron/: Compiles the real-weight blossom and matching-polytope proofs with exact source limits.

edmonds_1965_paths_trees_flowers/: The original blossom algorithm, odd-set matching duality and intrinsic matching decomposition, with complete local proof chains.

edwards_1973_extremal_properties_bipartite_subgraphs/: Proves sharp bounds tying a graph's edge count to the largest bipartite subgraph, giving the standard lower bound for maximum cuts.

elzahar_1985_existence_two_nonneighboring_subgraphs_graph/: Reduces the existence of a chromatic threshold forcing two non-neighboring n-chromatic subgraphs to excluded cliques of order at most n, proves it for n = 3, and bounds graphs with no two independent edges.

entringer_1972_number_unique_subgraphs_graph/: Constructs, for any c > (3/2)sqrt(2) and all large n, graphs on n vertices with more than 2^(n^2/2 - cn^(3/2)) subgraphs isomorphic to no other subgraph.

erdos_1959_maximal_paths_circuits_graphs/: Bounds the edge count of a graph without long paths or without long circuits, sharply for special orders, and determines it for large graphs with no path or circuit longer than 2k and for graphs with few independent edges.

erdos_1960_evolution_random_graphs/: Erdős and Rényi's 1960 study of the uniform random graph with n labeled vertices and N edges as N grows: thresholds for subgraphs, the sizes of the greatest tree and the greatest component with the double jump at N about n/2, the giant component of size G(c)n for c above 1/2, and the open problems of its last section, among them the order of magnitude of N(n) for a Hamilton-line.

erdos_1962_construction_certain_graphs/: Constructs graphs showing the Ramsey-type function h(k,l) exceeds l to the power 1 plus a constant, using regular simplices on a high-dimensional sphere.

erdos_1962_remarks_paper_posa/: Gives the sharp edge count forcing a Hamiltonian cycle in a graph of minimum degree at least k, sharpening Ore's theorem.

erdos_1962_theorem_rademacher_turan/: Proves that a graph on n vertices with floor(n^2/4)+t edges contains at least t*floor(n/2) triangles whenever t is below a constant times n.

erdos_1963_problem_graph_theory/: Shows that tournaments in which every k vertices are dominated by some vertex exist, with least order between 2^(k+1) - 1 and roughly 2^k k^2 log 2.

erdos_1964_extremal_problems_graph_theory/: Surveys how many edges force a prescribed subgraph, tabulating the extremal functions for small graphs and stating many open cases.

erdos_1964_extremal_problems_graphs_generalized_graphs/: Bounds the number of edges forcing a complete r-partite subhypergraph in an r-uniform hypergraph: an upper bound proved in full and a lower bound of the same shape, with an unspecified constant in the exponent, whose random-graph proof is only sketched.

erdos_1966_cliques_graphs/: Improves the lower bound of Moon and Moser on how many distinct clique sizes an n-vertex graph can have.

erdos_1966_existence_factor_degree_one_connected_random/: Shows a random graph on an even number of vertices almost surely has a perfect matching once its edge count passes the connectivity threshold.

erdos_1966_problem_graph_theory/: Determines asymptotically the most edges in a graph with no four-cycle, via a polarity graph of a finite projective plane.

erdos_1966_representation_graph_set_intersections/: Shows every graph on n vertices is the intersection graph of subsets of a ground set of [n²/4] elements, the integer part of n squared over four, and that no smaller ground set always suffices.

erdos_1967_extremal_problems_graph_theory/: Erdős's 1967 seminar lecture on extremal graph theory in a re-typeset archive copy: Turán-type results, the conjecture that rm vertices of degree at least m(r-1) force m disjoint complete r-graphs, the Bollobás-Erdős conjecture on m disjoint paths with its extremal example, the question whether 2n-2 edges force a cycle with a vertex adjacent to three of its points, and Pósa's arguments on disjoint cycles.

erdos_1967_recent_results_extremal_problems_graph_theory/: Surveys Turán-type extremal graph results and conjectures the possible exponents in the second-order term of the extremal edge count.

erdos_1969_uber_die_graphen_enthaltenen_saturierten_planaren/: Shows that a graph on n vertices with [n^2/4]+f(n) edges contains a saturated planar subgraph on more than c_1 f(n)/n vertices, sharp up to the constant.

erdos_1970_extremal_problems_graph_theory/: Extracts almost-regular subgraphs from dense graphs and uses them to disprove a conjectured form for bipartite extremal exponents.

erdos_1971_unsolved_problems_graph_theory_combinatorial_analysis/: A twenty-four item problem list on extremal graphs, cycles, planar subgraphs, set systems and colorings, with the known bounds for each.

erdos_1974_extremal_problems_graphs_hypergraphs/: A survey of Turan-type extremal problems for graphs and hypergraphs, listing known bounds and many unsolved questions.

erdos_1975_recent_progress_extremal_problems_graph_theory/: Survey of extremal graph problems, covering four-cycle-free graphs, regular subgraphs, forbidden bipartite graphs and several new conjectures.

erdos_1976_problems_results_combinatorial_analysis/: Erdős's Rome 1973 problem paper on extremal problems for graphs and hypergraphs, block designs and miscellaneous questions; p. 15 states the Erdős-Gallai conjecture that every graph on n vertices is covered by at most cn edge-disjoint circuits and edges, with the remark that only cn log n was proved.

erdos_1976_problems_results_graph_theory_combinatorial_analysis/: Erdős's 1975 Aberdeen problem paper; its Problem 29 defines the least edge count forcing two edge-disjoint circuits with the same vertex set, the origin of the same-vertex-set cycle problem, and its Problem 8 restates the girth-five orientation question of the 1971 list.

erdos_1978_problems_results_combinatorial_analysis_combinatorial_number/: A problem collection with prizes, proving a theorem on multiples of primes in short intervals and one on two-colorings of the subsets of a set with no k sets whose distinct unions all fall in one class.

erdos_1981_conjecture_hajos/: Shows almost all graphs refute the conjecture of Hajós, with chromatic number exceeding the largest clique subdivision by a factor of at least order root n over log n.

erdos_1982_compactness_results_extremal_graph_theory/: Erdős and Simonovits's 1982 Combinatorica paper stating the compactness conjecture for finite families of forbidden graphs, with compactness theorems for cycles and the exact (n/2)^{3/2}+O(n) bound for graphs with no four-cycle and no five-cycle.

erdos_1983_some_my_conjectures_number_theory_combinatorics/: Erdős's Boca Raton 1983 survey of his conjectures with recent progress, in a number theory part, a combinatorics part and a short closing part with a geometric problem and a number theory problem; item 6 of part II (p. 15) states the two Erdős-Gallai cycle covering conjectures, reports Pyber's proof of the n-1 bound and cites an unnamed example showing c >= 3/2 for the edge-disjoint form.

erdos_1984_cube_supersaturated_graphs_related_problems/: Proves recursion theorems giving random-graph-order counts of copies of degenerate bipartite graphs in supersaturated graphs, including the cube.

erdos_1985_note_size_chordal_subgraph/: Determines the edge threshold forcing a chordal subgraph with n edges and shows that for large n the same edge count forces one with n(1+ε) edges for some fixed ε > 0.

erdos_1986_asymptotic_number_graphs_not_containing_fixed/: Counts H-free graphs as two to the Turan number times one plus o of one when H is non-bipartite, and finds a hypergraph problem with no exponent.

erdos_1988_cycles_graphs_without_proper_subgraphs_minimum/: Studies graphs with 2n minus two edges having no proper subgraph of minimum degree three, showing they contain short cycles and a cycle of logarithmic length.

erdos_1988_problems_results_combinatorial_analysis_graph_theory/: Problem collection on strongly independent edges, minimal cuts, Ramsey numbers, regular subgraphs of dense graphs, and Turan numbers of bipartite graphs.

erdos_1989_number_distinct_induced_subgraphs_graph/: Shows a graph with few non-isomorphic induced subgraphs becomes almost canonical after deleting a small fraction of its vertices.

erdos_1989_radius/: Gives asymptotically sharp upper bounds on the diameter and radius of connected graphs in terms of order and minimum degree.

erdos_1990_subgraphs_minimal_degree_k/: Erdős, Faudree, Rousseau and Schelp's 1990 paper on the edge count that forces a subgraph of minimum degree k: the sharp threshold and the generalized wheel (Lemma 3), one edge more forcing such a subgraph missing about the square root of n over 6k cubed vertices (Theorem 1), the conjecture of Problem 814 that a constant fraction can be dropped, its proof when few vertices have degree exactly k (Lemma 4), and Theorem 2 on the edges forcing a subgraph on epsilon n vertices.

erdos_1992_covering_cliques_graph_vertices/: Studies the extremal behavior of the clique-transversal number, which earlier papers it cites had studied on restricted graph classes, and proves that every graph on n vertices has a clique-transversal of size at most n - sqrt(2n) + O(1).

erdos_1992_my_favourite_problems_various_branches_combinatorics/: A problem list reviewing progress on Erdos's Catania graph problems and posing new ones in graph theory, combinatorial number theory and geometry.

erdos_1993_my_favorite_solved_unsolved_problems_graph_theory/: Erdős's 1993 Quaestiones Mathematicae survey of his favorite graph problems, without proofs, in five chapters: Turán numbers of bipartite graphs and C_4, Ramsey numbers with the prize offers, Ramsey--Turán problems, critical and infinite chromatic graphs, and fourteen miscellaneous problems; cited as [Er93] on 31 problem pages.

erdos_1997_cycles_coprime_graph_integers/: Shows that a subset of one to n large enough to force a triangle in the coprime graph already forces all odd cycles up to length proportional to n.

erdos_1997_size_largest_bipartite_subgraphs/: Gives a constructive proof of the Edwards max-cut formula through maximum matchings and induced-star partitions.

erdos_1997_some_unsolved_problems/: Erdos's 1997 list of twenty-six problems in number theory, combinatorics, graph theory, geometry, analysis, set theory and group theory, read as a chapter of a whole-volume scan of the Cambridge tribute volume.

erdos_1998_decrease_diameter_triangle_free_graphs/: Introduces triangle-free-preserving diameter augmentation and proves sharp or asymptotic bounds for target diameters two, three, and five.

erdos_gyarfas_1999_split_balanced_colorings_complete_graphs/: Introduces split and balanced colorings, states the missing-color conjecture of Problem 617, and proves its r=3 and r=4 cases.

erdos_harary_tutte_1965_dimension_graph/: Erdős, Harary and Tutte's 1965 note defining the dimension of a graph, the least n such that the graph embeds in Euclidean n-space with every edge of length 1 and its vertices at distinct points: the values for complete graphs, complete graphs less an edge and complete bipartite graphs (dim K_{m,n} = 4 for m, n at least 3, the upper bound by Lenz's construction), wheels, cubes and the Petersen graph, the bound dim G at most twice the chromatic number, and two unsolved problems, on critical graphs and on graphs whose k-vertex subgraphs have bounded dimension.

fan_1987_diameter_2_critical_graphs/: Fan's 1987 paper on diameter 2-critical graphs: the Simon–Murty conjecture that such a graph on n vertices has at most [n^2/4] edges holds for n ≤ 24 and for n = 26 (the inequality, not the equality clause), and for n ≥ 25 such a graph has fewer than n^2/4 + (n^2 − 16.2n + 56)/320 < 0.2532 n^2 edges; it bears on Problem 742.

fan_1988_degree_sum_triangle_graph/: Fan's 1988 paper on the largest degree sum of a triangle: every graph with n vertices and e > n^2/4 edges has a triangle whose degrees sum to more than 21e/4n, so f(n, [n^2/4] + 1) > 21n/16 (Theorem 1, the lower bound of Problem 1033); the explicit construction giving f(n, e) < 4 sqrt(3e) − 2n + 5 for n^2/4 < e < n^2/3 (§ 2, the problem's upper bound); a second lower bound, better for e ≥ 0.26 n^2; and a new proof of Edwards's 6e/n for e ≥ n^2/3.

fan_2005_path_decompositions_gallai_s_conjecture/: Fan's 2005 paper on Gallai's path conjecture: the Main theorem, a graph on n vertices whose even-degree vertices induce an alpha-graph (built from the empty graph by adding isolated vertices and vertices joined to independent sets of a restricted kind) decomposes into floor(n/2) paths, and its Corollary, the same when each block of the even-degree subgraph is a triangle-free graph of maximum degree at most 3, strengthening Pyber's forest case.

faron_2019_clique_number_square_line_graph_relation/: Proves the clique number of the square of a line graph is at most four thirds of the squared maximum degree, improving the previous three halves bound.

faudree_1989_induced_matchings_bipartite_graphs/: Faudree, Gyárfás, Schelp and Tuza's 1989 note: the Erdős–Nešetřil strong chromatic index conjecture, dated to a Prague seminar of 1985 (Erdős's 1988 problem paper had printed it earlier), the extremal number kd² for bipartite graphs of maximum degree d with no induced (k + 1)-matching, the description of the extremal graphs, and the conjecture that bipartite graphs have strong chromatic index at most d².

fishburn_1983_balanced_integer_arrays_matrix_packing_theorem/: Fishburn's 1983 note proving Graham's degree-sequence form of the tree packing conjecture: vectors t^i of i positive integers summing to 2i − 1, for i = 1, ..., n, always fill the rows of an n × n matrix with every column sum n (Proposition 1), from Theorem 1, that every vector in (n, ..., 1) ⊕ (n − 1, ..., 1) is n-universal; with a conjecture on which column-sum vectors are n-universal. It contains no verification of the tree packing conjecture for any n.

fomin_2012_treewidth_computation_extremal_combinatorics/: Bounds the number of small connected separable vertex subsets by a binomial coefficient and uses it to compute treewidth in time O(1.7549^n).

ford_1956_maximal_flow_through_network/: Ford and Fulkerson (1956), real-capacity chain-flow duality, a finite ab-planar deletion procedure, and planar shortest-path reduction.

ford_1957_maximal_network_flows_hitchcock/: Ford–Fulkerson (1957): constructive integral flow and cut duality, network reductions and the complete transportation algorithm.

fox_2008_problem_duke_erdos_rodl_cycle/: Settles the Duke-Erdos-Rodl conjecture for beta < 1/5 by finding a strongly C8-connected subgraph with at least n^{2-2beta}/64 edges.

fox_2013_chromatic_number_clique_subdivisions_conjectures_hajos/: Proves the Erdos-Fajtlowicz conjecture that the chromatic number of an n-vertex graph is at most O(sqrt(n)/log n) times the order of its largest clique subdivision.

fox_2015_critical_window_classical_ramsey_turan_problem/: Gives nearly optimal bounds on the least independence number of dense K4-free graphs, solving the Bollobas-Erdos critical-window problems.

frankl_1984_exact_result_graphs/: Classifies all 3-graphs in which every four vertices span exactly zero or two edges and determines the densest such 3-graph.

furedi_1983_graphs_without_quadrilaterals/: Proves the Erdos conjecture f(q^2+q+1) = q(q+1)^2/2 when q is a power of 2, and the upper bound for every even q.

furedi_1991_turan_type_problem_erdos/: Proves that any graph on n vertices with at least k^{3/2} n^{3/2} edges contains the graph formed by the lowest three levels of the Boolean lattice.

furedi_1992_maximum_number_edges_minimal_graph_diameter/: Proves the Murty-Simon conjecture for large n: a minimal diameter-2 graph on n vertices has at most n^2/4 edges, with equality only for the balanced complete bipartite graph.

furedi_1994_maximal_triangle_free_graphs_restrictions_degrees/: Studies the least number of edges in a maximal triangle-free graph on n vertices with maximum degree at most D, exactly for D >= (n-2)/2 and large n, asymptotically for linear D, and up to a constant factor for D = cn^eps with 1/2 < eps < 1, and constructs for every large n a triangle-free graph of diameter 2 on n vertices with maximum degree at most (2/sqrt(3))(sqrt(n) + n^(7/24)).

furedi_2006_turan_number_hexagon/: Gives hexagon-free constructions and bounds, with a bipartite construction disproving the proposed constant for simultaneous C5 and C6 avoidance.

furedi_2015_proof_stability_extremal_graphs_simonovits_stability_from_szemeredis_regularity/: Gives finite edit bounds from near-extremal clique-free graphs to multipartite graphs.

furedi_2021_hypergraphs_without_exponents/: Gives short proofs that for every k at least 5 there is a single k-uniform hypergraph whose Turan function has no polynomial order of magnitude.

furedi_ramamurthi_2002_splittable_colorings_graphs_hypergraphs/: Source record and research digest.

galvin_2025_trees_non_log_concave_independent_set_sequences/: Constructs trees whose independent set sequence fails log-concavity about α/(16 log α) below the independence number α, inside the decreasing tail, so E993 gains no non-unimodal tree.

gaspers_2018_number_minimal_separators_graphs/: Gives a simple proof that an n-vertex graph has O(rho^n n) minimal separators, rho the golden ratio, and states a lower bound omega(1.4521^n) whose printed separator count fails; the journal version states omega(1.4457^n).

george_khodkar_wallis_2016_minimal_pancyclicity/: Chapter 4, Minimal Pancyclicity, of George, Khodkar and Wallis's 2016 SpringerBrief, on the least excess m(n) of a pancyclic graph on n vertices (the problem's h(n)): the exact values for n ≤ 37, Theorem 17 (m(n) ≤ m(n − 1) + 1), a critique of Sridharan's 1978 construction, and the general upper bounds of Theorems 18 and 19, an excess of at most 2^h + 2h on stated windows of n; the chapter prints no logarithmic bound and does not restate Bondy's.

gishboliner_2025_induced_subgraphs_k_r_free_graphs_erdos_rogers/: Proves that for every r ≥ 4 and every K_{r−1}-free graph F the largest F-free induced subgraph guaranteed in a K_r-free graph on n vertices has order O(n^{1/2−ε_F}), tight in two senses; its introduction surveys the Erdős–Rogers function f_{3,4}, the site's Problem 620.

goedgebeur_2025_improved_lower_bounds_maximum_size_graphs/: A hill-climbing search improves the best known lower bounds on the maximum number of edges in a girth-five graph for nearly all n from 74 to 198.

gordeev_2023_combinatorial_nullstellensatz_turan_numbers_complete_r/: Uses a generalized Combinatorial Nullstellensatz to give a short polynomial construction for the Erdos box problem lower bound.

graham_1971_constructive_solution_tournament_problem/: Gives an explicit Paley tournament in which every k vertices are dominated by a common vertex, for primes congruent to 3 modulo 4 above k squared times 2^(2k-2).

griffin_2013_minimal_pancyclicity/: Determines the least number of edges in a pancyclic graph on n vertices for all n up to 37, proves Bondy's stated lower bound, and proves partial cases of monotonicity.

grigorescu_2003_decreasing_diameter_cycles/: Sharpens unrestricted diameter-two and diameter-three augmentation bounds for cycles.

grzesik_2012_maximum_number_five_cycles_triangle_free/: Proves Erdős's conjecture that a triangle-free graph on n vertices has at most (n/5)^5 cycles of length five.

grzesik_2019_minimum_number_edges_that_occur_odd/: Determines the minimum number of edges lying in a copy of a given odd cycle in graphs with more than n^2/4 edges: asymptotically for pentagons, exactly for longer odd cycles at large orders.

guichard_1990_note_packing_complete_graphs_trees/: Guichard and Massman's 1990 note verifying by computer that the Gyárfás–Lehel tree packing conjecture holds through n = 11, and finding that Fishburn's universally recursive families are unlikely to prove it in general.

gyarfas_1998_generalized_split_graphs_ramsey_numbers/: Source record and research digest.

gyarfas_2023_problems_close_my_heart/: Source record and research digest.

gyarfas_et_al_2002_finite_basis_characterization_split_colorings/: Source record and research digest.

gyori_2017_number_edge_disjoint_triangles_k_4_free_graphs/: Proves Győri's conjecture, open for about 25 years: floor(n^2/4)+k edges on n vertices force k edge-disjoint triangles in a K_4-free graph.

hao_2026_strong_chromatic_index_bipartite_graphs/: A 2026 preprint of Hao, Yang and Yu bounding the strong chromatic index of a bipartite graph by 1.676 times the product of the two sides' maximum degrees when both are large, toward the Brualdi–Quinn Massey conjecture Δ_A Δ_B; unrefereed.

hatami_2013_number_pentagons_triangle_free_graphs/: Bounds every triangle-free graph's pentagon count by (n/5)^5, classifies equality, and gives the rounded exact maximum for sufficiently large n.

haviv_2018_symmetric_complete_sum_free_sets_cyclic/: Constructs symmetric complete sum-free sets in finite cyclic groups, with relative sizes dense in [0,1/3], exponentially many of them, and some of size O(sqrt(n)) in every large Z_n.

haxell_1999_packing_covering_triangles_graphs/: Haxell's 1999 note proving the first nontrivial general bound toward Tuza's conjecture: every graph G has a set of at most (3 - ε)ν(G) edges meeting every triangle, where ν(G) is the largest number of edge-disjoint triangles and ε ≥ 3/23, that is τ(G) ≤ (66/23)ν(G); with a closing remark that induction improves ε to (23 - sqrt(481))/8.

haxell_2006_odd_independent_transversals_are_odd/: Determines the exact maximum degree threshold forcing an independent transversal in r-partite graphs for odd r, showing it equals the threshold for r-1 parts.

heilman_2020_independent_sets_random_trees_sparse_random_graphs/: Proves that a uniformly random labelled n-vertex tree has strictly increasing independent set counts up to size floor(0.26543n) with probability at least 1 - e^{-cn}, gives increasing and decreasing ranges for sparse random graphs, and does not settle Problem 993.

hofmeister_1998_k_partite_subgraphs/: Gives lower bounds for large k-partite subgraphs, generalizing the Edwards maximum-cut bound; written out, its k=2 case is parity-sensitive.

horak_1993_induced_matchings_cubic_graphs/: Horák, He and Trotter's 1993 theorem that the edges of every graph of maximum degree at most three can be partitioned into ten induced matchings, the first nontrivial case of the Erdős–Nešetřil strong edge-coloring conjecture, best possible and obtained independently by Andersen.

house_2013_4_dimensional_graph_has_at_least_9_edges/: House's 2013 note answering Erdős's question on the smallest number of edges of a graph of unit-distance dimension 4: the minimum is 9, and K_{3,3} is the only 4-dimensional graph with 9 edges, by a reduction to 43 biconnected candidate graphs and a drawn embedding of each of the other 42 in the plane or in 3-space.

huang_2018_strong_chromatic_index_graphs_maximum_degree_four/: Huang, Santana and Yu's 2018 theorem that every graph (multigraph) of maximum degree four has strong chromatic index at most 21, one above the Erdős–Nešetřil conjecture's 20, improving Cranston's 22 and Horák's 23, at the case the paper calls the first unsolved one.

hurley_2022_improved_procedure_colouring_graphs_bounded_local_density/: Improves chromatic number bounds for locally sparse graphs, yielding a strong chromatic index bound of 1.772 times the squared maximum degree.

janzer_2019_improved_bounds_extremal_number_subdivisions/: Proves that, for each integer t at least 3, n-vertex graphs avoiding the subdivision of the complete graph on t vertices have at most C_t n^{3/2 - 1/(4t-6)} edges.

janzer_2021_extremal_number_longer_subdivisions/: Proves the two Conlon–Lee conjectures on the extremal number of the (k − 1)-subdivision of a multigraph for even k; its introduction states the Kostochka–Pyber theorem that 4^{t²} n^{1+ε} edges force a subdivided K_t on at most 7t² log t / ε vertices, answering Erdős's question on planar subgraphs.

janzer_2022_turan_number_hypercube/: Gives the first power improvement for the Turan number of the d-dimensional hypercube and near-optimal bounds for rainbow-cycle-free proper edge colorings.

janzer_2023_disproof_conjecture_erdos_simonovits_turan_number/: Disproves the Erdős-Simonovits conjecture by constructing 3-regular bipartite graphs whose Turán number is at most n^{4/3+eps}.

janzer_2023_rainbow_turan_number_even_cycles_repeated/: Proves the rainbow Turán number of the cycle of length 2k is O(n^{1+1/k}), settling a conjecture, and derives several further extremal results.

janzer_2023_resolution_erdos_sauer_problem_regular_subgraphs/: Proves that every n-vertex graph with average degree at least C(k) log log n contains a k-regular subgraph, matching the Pyber-Rodl-Szemeredi lower bound, and finds an almost-regular subgraph with nearly m root log m edges in every graph with n log n edges.

janzer_2024_packing_largest_trees_tree_packing_conjecture/: Proves Bollobas's conjecture by packing a linear number of the largest trees from the tree packing conjecture into the complete graph.

janzer_2025_power_saving_brown_erdos_sos_problem/: Proves the first power-saving bound near the Sárközy-Selkow threshold for the Brown-Erdős-Sós problem on 3-uniform hypergraphs, at the cost of an additive constant of 38.

jeffries_2026_schutte_s_property_sets_tournaments_application/: Generalizes Schutte's domination property to sets of tournaments, bounding the least vertex count f(m,k) and building new unfair dice games.

jiang_2020_negligible_obstructions_turan_exponents/: Realizes infinitely many new rational Turan exponents by single graphs, verifying the Bukh-Conlon conjecture for a family of rooted trees.

jiang_2020_turan_numbers_bipartite_subdivisions/: Proves the Conlon-Janzer-Lee bound on Turan numbers of subdivided complete bipartite graphs for path length 3 and 4, giving new Turan exponents.

jiang_2022_turan_exponents_bipartite_graphs/: Realizes the new Turan exponents 2-2/(2s+1) and 7/5 by single bipartite graphs, extending the known cases of the Erdos-Simonovits conjecture.

jiang_2023_many_turan_exponents_via_subdivisions/: Shows 1+p/q is a Turan exponent whenever q > p^2, realized by unevenly subdivided complete bipartite graphs.

jiang_2025_regularization_asymmetric_extremal_numbers_subdivisions/: Strengthens the Erdos-Simonovits regularization theorem, proves a bipartite (biregularization) analogue, and uses the analogue to bound edge counts of bipartite graphs with no even subdivision.

jiang_2026_rational_exponents_near_3_2/: Proves the rational exponents conjecture for the two-parameter family of exponents 1 + (rt-1)/(2rt+2r), t at least 2 and r at least 2t+3, by bounding the Turan number of rooted powers of the subdivided height-two tree.

joos_2019_optimal_packings_bounded_degree_trees/: Proves the Gyarfas-Lehel tree packing conjecture and Ringel's conjecture for all bounded degree trees and large n.

joos_2022_ramsey_theory_constructions_hypergraph_matchings/: Uses conflict-free hypergraph matchings to build asymptotically optimal generalized Ramsey colorings of complete and complete bipartite graphs.

joret_2021_tight_bounds_clique_chromatic_number/: Proves that every graph of maximum degree Δ has clique chromatic number at most (1 + ε)Δ/log Δ once Δ is large and, as a corollary, that every graph on n vertices has clique chromatic number O(√(n/log n)); the corollary is the theorem behind the site's resolution of Problem 610.

kadrawi_levit_2023_independence_polynomial_trees_is_not_always_log_concave_starting_from_order_26/: Gives two 26-vertex trees and infinite tree families whose independence polynomials fail log-concavity; the 26-vertex examples stay unimodal, and the paper gives no counterexample to E993.

kahn_2022_tuza_s_conjecture_random_graphs/: Shows the random graph G(n,p) satisfies, with high probability, Tuza's conjecture that triangle cover number is at most twice the triangle matching number, for every p.

kang_2021_rational_turan_exponents_conjecture/: Shows 2 - a/b is a realizable Turan exponent whenever b > a and b is congruent to plus or minus 1 mod a, giving infinitely many limit points.

kang_pikhurko_2005_maximum_k_r_1_free_graphs_which_are_not_r_partite/: Source record and research digest.

kara_2026_machine_verified_fixed_r5_erdos_617/: Formally verifies the fixed five-color case of Problem 617 in Lean, with LRAT-certified finite endpoints and an explicit statement boundary.

keevash_2006_sparse_halves_triangle_free_graphs/: Proves Erdos's conjecture that a triangle-free graph has half its vertices spanning at most n^2/50 edges when it has at most n^2/12 or at least n^2/5 edges.

keevash_2020_brown_erdos_sos_conjecture_hypergraphs_large/: Proves the Brown-Erdos-Sos conjecture for linear hypergraphs whose uniformity is large enough in terms of the linear density.

khadzhiivanov_1988_maximal_number_triangles_common_edge/: Khadzhiivanov's 1988 account, in Russian, of the largest number of triangles on one edge of a graph: the inequality (3t + t̄) t̂ ≥ nt, its extremal graphs, the corollary that more than n²/4 edges force an edge on more than n/6 triangles (Erdős's problem, solved with Nikiforov in 1979), and a critical reading of Edwards's announcement.

kierstead_2010_fast_algorithm_equitable_coloring/: Kierstead, Kostochka, Mydlarz and Szemerédi's 2010 Combinatorica paper, which restates the Hajnal–Szemerédi theorem (every graph of maximum degree at most r has an equitable coloring with r+1 colors, conjectured by Erdős) as its Theorem 1, gives a new proof of it and turns the proof into an algorithm running in time O(rn²).

komlos_szemeredi_1983_limit_distribution_hamiltonian_cycles_random_graph/: Komlós and Szemerédi's 1983 limit law for Hamiltonicity of the random graph: with (1/2) n log n + (1/2) n log log n + c n edges the probability of a Hamiltonian cycle tends to exp(-exp(-2c)) (Theorem 1), and that of a Hamiltonian path to (1 + e^{-2c} + e^{-4c}/2) exp(-exp(-2c)) (Theorem 2); the minimum-degree-2 condition is almost surely sufficient.

korshunov_1976_solution_problem_erdos_renyi_hamiltonian_cycles/: Korshunov's 1976 Doklady announcement that almost all graphs with n labeled vertices and k edges are Hamiltonian, and pancyclic, exactly when k = (n/2)(ln n + ln ln n + φ(n)) with φ(n) → ∞, with a sketch of the polynomial-time path-rotation algorithm the proof uses for k > 3n ln n, and no proofs.

korshunov_1985_new_version_solution_problem_erdos_renyi_hamiltonian_cycles/: Korshunov's 1985 English paper giving a new proof of his theorem that almost every graph with n vertices and k edges contains a Hamiltonian cycle if and only if k = (n/2)(log n + log log n + φ(n)) with φ(n) → ∞, the Erdős–Rényi problem of Problem 746: Theorem 1, proved through its binomial-model form Theorem 2 by stable paths and permissible transformations, with a closing comment placing the 1976 announcement, the 1977 Russian paper and Komlós and Szemerédi's independent solution.

kostochka_pyber_1988_small_topological_complete_subgraphs_dense_graphs/: Kostochka and Pyber's 1988 theorem that every graph on n vertices with 4^{t²} n^{1+ε} edges contains a topological complete graph TK_t on at most 7t² log t / ε vertices, answering Erdős's 1971 question whether n^{1+ε} edges force a non-planar subgraph of bounded order (the case t = 5).

kostochka_yancey_2012_ores_conjecture_color_critical_graphs_is_almost_true/: Sharp lower bounds for the number of edges in a color-critical graph.

kovari_1954_problem_k/: Bounds the number of ones forcing a j-by-j all-ones submatrix in an n-by-n zero-one matrix, giving the classical n to the two minus one over j bound.

kratzke_1988_eigensharp_graphs_decomposition_complete_bipartite/: Studies the graphs whose minimum number of edge-disjoint complete bipartite subgraphs partitioning the edges equals the eigenvalue lower bound; its introduction records Erdős's conjecture that this number is n minus the independence number for almost all graphs, the origin of Problem 807.

krivelevich_1994_free_graphs_without_large_free_subgraphs/: Improves both bounds on the largest K^r-free induced subgraph forced in a K^s-free graph on n vertices: the lower bound through the Ajtai–Erdős–Komlós–Szemerédi independence bound, the upper bound by a random-graph construction.

krivelevich_1995_edge_distribution_triangle_free_graphs/: Improves the local-density threshold forcing a triangle to n^2/36 for half-sized sets and quantifies uneven edge spread in triangle-free graphs.

kuhn_fable_2026_counterexample_erdos_problem_619/: Gives connected triangle-free graphs whose triangle-free diameter-four augmentation number is n-o(n), disproving Erdős Problem 619.

kumar_2026_improved_bound_strong_clique_index_graphs/: A July 2026 preprint of Kumar, Mohar and Pragada bounding the strong clique index by 2607/1987 times the squared maximum degree, below the 4/3 of Faron and Postle, and refuting two conjectures of Cambie, Cames van Batenburg, de Joannis de Verclos and Kang on the t = 3 Erdős–Nešetřil edge-distance function, with h_3(4) ≥ 71 from the odd graph O_4 and liminf h_3(Δ)/Δ³ ≥ 253/225; unrefereed, with a declared use of AI tools in its ideation.

lazebnik_ustimenko_woldar_1994_properties_certain_families_2k_cycle_free_graphs/: Lazebnik, Ustimenko and Woldar's 1994 note: for k >= 3 and 2 <= t <= k - 1, taking t copies of each vertex in the smaller part of a bipartite 2k-cycle-free graph of girth at least 2k + 2 gives bipartite 2k-cycle-free graphs of the same magnitude r and constant at least t (2/(t+1))^r times the old one, so C_2k-extremal graphs are eventually non-bipartite or of girth at most 2k - 2; applied to the known girth-eight and girth-twelve families, lambda_3 >= 2/3^(4/3) and lambda_5 >= 4/5^(6/5), whose bipartite graphs disprove Problem 574 at k = 3 and k = 5 by the corpus's deduction.

leonard_1972_graphs_at_most_four_line_disjoint_paths_connecting_any_two_vertices/: Leonard's 1972 determination of l_5(n), the least number of edges forcing two vertices joined by five edge-disjoint paths in a graph on n vertices: l_5(2n) = 5n − 2 and l_5(2n + 1) = 5n + 1 for n at least 3, with the observation that l_r(n) = k_r(n) for r at most 4, so that the edge-disjoint and vertex-disjoint thresholds first differ at r = 5, and the closing formula l_r(n) = [(r(n − 1) + 2)/2] proved for r at most 5 and asked for r above 5.

leonard_1973_conjecture_bollobas_erdos/: Leonard's 1973 note disproving the Bollobás–Erdős conjecture at m = 5 under the vertex-disjoint reading: a graph G with 57 points and 141 edges and no two points joined by five internally disjoint paths, and graphs with n points and more than [5n/2] + s edges and no such pair for every s, so that k_5(n) is not a linear function of n with coefficient 5/2; with the suspicion that the edge-disjoint form of the conjecture holds.

leonard_1973_graphs_ways/: Shows that 3n-2 edges is the exact threshold forcing two vertices joined by six edge-disjoint paths in a graph on n vertices.

letzter_et_al_2026_nearly_hamilton_cycles_sublinear_expanders_applications/: Nearly covers regular graphs of at least polylogarithmic degree with disjoint subdivisions of any fixed graph, and shows n(log n)^130 edges force a cycle with at least as many chords as vertices, bounding E642.

levit_mandrescu_2002_unimodality_independence_polynomials_some_well_covered_trees/: Proves that well-covered spiders, centipedes and joined centipedes have unimodal independence polynomials, settling tree families for E993 without proving it for all trees and forests.

levit_mandrescu_2004_very_well_covered_graphs_unimodality_conjecture/: Proves that the independent set counts of bipartite graphs, so of forests, do not increase from index ⌈(2α-1)/3⌉ on, and that very well-covered graphs with α ≤ 9 are unimodal, giving E993 a tail but no rising prefix.

li_2023_stability_woodall_theorem_spectral_conditions_large_cycles/: Gives tight spectral radius conditions for cycles of length up to n − k + 1, a stability version and a refinement of Woodall's 1972 theorem, and a spectral condition for the circumference of 2-connected graphs; it restates Woodall's theorem, that a graph on n at least 2k + 3 vertices with more than C(n−k−1, 2) + C(k+2, 2) edges contains cycles of every length from 3 to n − k, beside Erdős's question.

li_2026_unimodality_independence_polynomials_two_family_trees/: Claims unimodality of the independence polynomials of two three-branch tree families by pairing negative Schur coefficients, one displayed pairing map failing as printed; the families do not settle Problem 993.

liu_2021_geometric_constructions_ramsey_turan_theory/: Constructs Bollobas-Erdos graphs of all rational densities, fixing several Ramsey-Turan densities and refuting the conjectured periodic structure.

liu_2025_complement_erdos_hajnal_problem_paths_equal_degree/: A preprint extending Chen and Ma's theorem to every n at least 2: the unique graph on 2n + 1 vertices with at least n² + n edges and no two equal-degree vertices joined by a path of length three is K_{n,n+1}, with the even-order analog for n at least 3.

lovasz_1983_number_complete_subgraphs_graph_ii/: Lovász and Simonovits's 1983 chapter on the minimum number of complete p-graphs in a graph with given numbers of vertices and edges, whose abstract states the proof of the Erdős-Rademacher triangle conjecture.

ma_2023_upper_bounds_extremal_number_4_cycle/: Disproves Erdos's 1970s conjecture that ex(n,C4) equals n^{3/2}/2 + n/4 + o(n) and gives upper bounds near projective-plane orders.

ma_2025_erdos_problem_1034/: A three-page note disproving the Erdős–Faudree conjecture of Problem 1034 by an explicit construction: graphs with more than n²/4 edges in which every triangle has at most (2 − √(5/2) + o(1))n vertices joined to two of its vertices; it also quotes Erdős's 1993 passage and records the bounds (1/6 − o(1))n ≤ h(n) ≤ (2 − √(5/2) + o(1))n for the general question.

ma_2025_extremal_numbers_triangle_plus_four_cycle/: Gives, for every n at least 7, a girth-five graph on n vertices with c n to the five quarters more edges than the bipartite four-cycle-free maximum, the first improvement of the girth-five lower bound since 1976.

mader_1967_homomorphieeigenschaften_und_mittlere_kantendichte_von_graphen/: Mader's 1967 note proving that average edge density alone forces complete minors and complete topological subgraphs: Satz 1, 2^(n-3) times the order in edges gives the complete graph on n vertices as a minor, and Satz 2, 2^(C(n-1,2)-1) (n-1) times the order in edges gives a subdivision of it, the first edge bound for Problem 718's question; with bounds on the minimum-degree and edge-density thresholds for a complete minor.

mader_1973_ein_extremalproblem_des_zusammenhangs_von_graphen/: Mader's 1973 paper settling the edge-disjoint form of the Bollobás–Erdős conjecture for every n: Satz 1, a finite graph on at least n vertices with more than (n/2)(e(G) − 1) − (1/2)σ_n(G) edges has two vertices joined by n edge-disjoint paths, with the exact threshold [(n/2)(m − 1)] + 1 as its Korollar; and examples showing that no constant c_n makes (n/2)e(G) + c_n edges force n internally disjoint paths, for odd n ≥ 5 and even n ≥ 6; with Satz 2, a girth-restricted vertex-disjoint bound.

malekshahian_2026_clique_building_game_erdos/: Gives the first progress on three clique- and degree-building games of Erdos, showing the second player wins for most values of n.

milanic_2024_upper_clique_transversal_problem/: Milanič and Uno's 2024 preprint introducing the upper clique transversal number, the largest size of a minimal set of vertices meeting every maximal clique: NP-complete to decide in chordal, chordal bipartite, cubic planar bipartite and line graphs of bipartite graphs, linear time in split, proper interval and cographs, polynomial for bounded cliquewidth; algorithmic literature adjacent to Problem 151, not bearing on its inequality.

molloy_reed_1997_bound_strong_chromatic_index_graph/: Molloy and Reed's 1997 proof that the strong chromatic index of a graph of sufficiently large maximum degree Δ is at most 1.998 Δ², the first bound below the trivial 2Δ² and the answer to the 1985 question of Erdős and Nešetřil whether any (2 − ε)Δ² holds; proved by a sparsity lemma for the neighborhoods in the square of the line graph and a probabilistic coloring lemma for graphs with sparse neighborhoods, the method every later bound on the problem refines.

moon_moser_1965_cliques_graphs/: Moon and Moser's 1965 paper on cliques, the maximal complete subgraphs of a graph: the maximum number f(n) of cliques in a graph on n nodes with its extremal graphs (Theorems 1 and 2), and the bounds n − [log n] − 2[log log n] − 4 ≤ g(n) ≤ n − [log n], logarithms base 2, on the maximum number g(n) of different clique sizes in a graph on n nodes (Theorems 3 and 4), the origin of Problem 927.

morris_2016_number_free_graphs/: Proves there are at most 2^{O(n^{1+1/l})} graphs on n vertices with no cycle of length 2l, confirming a conjecture of Erdős.

mousset_2017_smaller_subgraphs_minimum_degree/: Shows a graph with one edge more than the threshold forcing minimum degree k has such a subgraph on all but Omega(n/log n) vertices.

mubayi_2024_order_erdos_rogers_functions/: Proves the Erdős-Rogers function satisfies f_s(n) = O(sqrt(n) log n) for every fixed s at least 3, nearly matching the known lower bound.

nagy_2011_multipartite_turan_problem_density_eigenvalues/: Determines the critical edge density for transversal copies of trees and cycles in weighted multipartite blow-ups, relating the threshold to the largest adjacency eigenvalue and to maximum degree.

nagy_2017_supersaturation_zarankiewicz_towards_erdos_simonovits_sidorenko/: Determines the number of four-cycles forced in bipartite graphs whose edge count exceeds the Zarankiewicz number by at most n, for n = q^2+q+1 with q a prime power, with asymptotically sharp results for K_{2,t}.

narins_2017_graphs_without_proper_subgraphs_minimum_degree/: Disproves the Erdos-Faudree-Gyarfas-Schelp conjecture on cycle lengths in degree 3-critical graphs by building ones with no 23-cycle.

nenadov_2025_improved_bound_number_cycle_sets/: Shows that graphs on n vertices realize at most 2^(n - n^(1/2-o(1))) distinct cycle sets, improving Verstraëte's earlier bound.

nesetril_1978_probabilistic_graph_theoretical_method/: Gives a short probabilistic method for sparse hypergraphs of large chromatic number and for graphs of large girth that contain a prescribed ordered cycle under every vertex ordering, hence are not subgraphs of any Hasse diagram.

nguyen_2024_problem_el_zahar_erdos/: Proves minimum-degree variants of the El-Zahar-Erdos problem on finding two anticomplete subgraphs of large chromatic number.

nguyen_2026_induced_subgraph_density/: Proves the Erdos-Hajnal conjecture for the five-vertex path, completing the conjecture for all five-vertex graphs.

norin_2015_sparse_halves_dense_triangle_free_graphs/: Proves Erdős's sparse-halves conjecture for triangle-free graphs of minimum degree at least 5n/14, for those with at least (1/5 - gamma)n^2 edges, and for those close in edit distance to a balanced blowup of the Petersen graph.

norin_2016_triangle_independent_sets_vs_cuts/: Proves the sharp triangle-independent-set and cut inequality, its exact equality classification, and the source’s constructive and local corollaries.

openai_2026_linear_cycle_edge_decomposition_graph/: A 32-page manuscript of the OpenAI mathematics release claiming that every n-vertex graph has an edge partition into at most Cn cycles and single edges, for an absolute C, by a multiscale induction built on the Bucić-Montgomery expansion and routing method; the claim is Problem 184.

openai_2026_logarithmic_independence_bound_clique_free_graphs/: A twenty-one-page manuscript of the OpenAI mathematics release claiming that every K_r-free graph with average degree d at least 2 has an independent set of size at least c_r n log d/d for each fixed r at least 4, the statement of Problem 802, by a weighted triangle bound; the release lists a Lean file.

openai_2026_sharp_terminal_leave_random_triangle_removal/: Claims that the edge count left by uniform random triangle removal from K_n, divided by n^(3/2), converges in L^2 to 1/(2 sqrt 2), the triangle case of the Joos-Kuhn sharp-constant conjecture, by a priority-scan continuation after a Joos-Kuhn prefix; bears on 1155.

ore_1961_arc_coverings_graphs/: Ore's 1961 paper on arc coverings of graphs: a maximal covering by k ≥ 2 disjoint arcs forces k ≤ n − ρ(t) − ρ(t′) for terminal vertices t, t′ of two different arcs, hence ρ(a) + ρ(b) ≥ n − 1 for all nonadjacent pairs gives a Hamilton arc, and the sharp edge counts (n − 1)(n − 2)/2 + 1 for a Hamilton arc and (n − 1)(n − 2)/2 + 2 for a Hamilton circuit, with the extremal graphs.

posa_1976_hamiltonian_circuits_random_graphs/: Pósa's 1976 proof that a random graph on n vertices with [c_1 n log n] edges contains a Hamiltonian circuit with probability tending to 1 for a sufficiently large constant c_1 (Theorem 3), by way of the rotation lemma on the end points of longest paths (Lemma 1) and a Hamiltonian line in the binomial random graph with edge probability (c log n)/n (Theorem 1).

pyber_1995_dense_graphs_without_3_regular_subgraphs/: Pyber, Rödl and Szemerédi's 1995 lower bound for the Erdős–Sauer problem: a random bipartite construction of graphs with cn log log n edges and no 3-regular subgraph, hence none k-regular for any k ≥ 3, so Pyber's 32k²n log n upper bound cannot be improved to O(n); with the upper bound c_k n log Δ(G) edges force a k-regular subgraph, the very dense case ex(n, f(c)n-reg) ≤ cn², and closing remarks on cycles with diagonals, two edge-disjoint cycles on one vertex set, and induced regular subgraphs.

pyber_1996_covering_edges_connected_graph_paths/: Pyber's 1996 paper on Gallai's path conjecture: Theorem 0, a graph in which every cycle contains a vertex of odd degree (the even-degree vertices induce a forest) is covered by floor(n/2) edge-disjoint paths, shown best possible by K_{2m+1} minus m-1 independent edges, an odd semi-clique; Theorem I, every connected graph on n vertices is covered by n/2 + O(n^(3/4)) paths that may share edges; Theorem II, n/2 + 4e/n paths for e edges; and the example showing that no asymptotic form of Gallai's conjecture is weaker than the conjecture.

ramos_sun_2025_ai_enhanced_approach_tree_unimodality_conjecture/: Reports a transformer-guided search finding tens of thousands of trees with non-log-concave independence sequences on 27 to 101 vertices; it reports no tree whose sequence fails unimodality, the property Problem 993 asks about.

razborov_2010_3_hypergraphs_forbidden_4_vertex_configurations/: Proves by flag algebras that a 3-graph with no four independent vertices and no four vertices spanning exactly three edges has edge density at least 4/9 - o(1), the Turan density 5/9 in complementary terms, and reports a numerical bound for the unrestricted tetrahedron problem.

razborov_2022_more_about_sparse_halves_triangle_free/: Improves the bound on sparse halves in triangle-free graphs to 27n^2/1024 edges and proves the Erdos conjecture in several graph classes.

reed_stein_2026_erdos_sos_conjecture_dense_graphs/: Reed and Stein's proof of the Erdős–Sós conjecture for dense host graphs: for each γ > 0 and all large n, every n-vertex graph with average degree exceeding k − 2 contains every k-vertex tree once k ≥ γn (Theorem 2), and the multicolor tree Ramsey bound R_ℓ(T) < ℓ(k − 2) + 3 for every ℓ ≥ 2 and every k-vertex tree T once k ≥ k_0(ℓ) (Corollary 4), the answer to the question of Problem 557.

ren_2024_extremal_triangle_free_graphs_chromatic_number/: Shows a triangle-free graph on n >= 90 vertices with chromatic number at least four has at most floor((n-3)^2/4)+5 edges, attained by Grotzsch blow-ups.

sarkozy_1999_complete_tripartite_subgraphs_coprime_graph_integers/: Shows that for large n every set of integers up to n with more than f(n,2) elements, the number divisible by 2 or 3, has a coprime graph containing a complete tripartite subgraph K(1, l, l) with l of order log n / log log log n.

sauermann_2019_rousseau_schelp_subgraphs_minimum_degree/: Proves that, for k at least 3, one edge above the extremal bound forces a subgraph of minimum degree at least k on a constant fraction fewer vertices.

shapira_2023_new_approach_brown_erdos_sos_problem/: Reduces a constant-deficiency form of the Brown-Erdos-Sos conjecture to a weakened Turan-type conjecture about 2-degenerate bipartite graphs.

shearer_1995_independence_number_sparse_graphs/: Shearer's 1995 note proving that a K_r-free graph (r at least 4) on n vertices with maximum degree d, or with average degree d, has an independent set of at least c(r) n ln d/(d ln ln d) vertices for large d, by an entropy count of independent sets; it improves the ln ln d/d bound of Ajtai, Erdős, Komlós and Szemerédi and leaves their ln d/d question open.

shelah_1998_erdos_renyi_conjecture/: Proves that a graph on n vertices with no clique or independent set of size c1 log n has at least 2^(c2 n) non-isomorphic induced subgraphs.

simonovits_1974_extremal_graph_problems_symmetrical_extremal_graphs/: Simonovits 1974: when one forbidden graph is almost d-chromatic, some extremal graph, also under a chromatic condition such as chromatic number at least t, lies in a class of very symmetric graphs (Theorems 1.a, 1-3); with Theorem 2.7, from his thesis, that the most edges in a triangle-free graph on n vertices with chromatic number at least t is n^2/4 - ĝ_3(t) n/2 + O(1), and Remark 2.8's bounds on ĝ_3(t).

sleszynskanowak_2016_clique_number_square_line_graph/: Proves the clique number of the square of the line graph of any simple graph is at most 1.5 times the square of the maximum degree, re-proves the bipartite bound, and derives a 1.75 bound on the fractional strong chromatic index.

sneiderman_2026_five_color_case_balanced_coloring/: Proves the fixed five-color case of Problem 617 and the sharp identity R(6;5,4)=26 by a finite extremal graph argument.

sneiderman_2026_nine_color_case_balanced_coloring/: Gives a computer-assisted proof of the fixed nine-color case of Problem 617 through finite classifications and LRAT-certified terminal branches.

sneiderman_2026_seven_eight_color_cases_balanced_coloring/: Gives computer-assisted proofs of the fixed seven- and eight-color cases of Problem 617, including finite enumeration and LRAT-certified endpoints.

sneiderman_2026_six_color_case_balanced_coloring/: Proves the fixed six-color case of Problem 617 using a least-color reduction and explicit finite graph classifications.

sorensen_thomassen_1974_k_rails_graphs/: Sørensen and Thomassen's 1974 determination of f_5(n), the least number of edges forcing a 5-rail (two vertices joined by five internally disjoint paths) in a graph on n vertices: f_5(n) = [8n/3] − 3 for n at least 6, n not 7 or 12; the Bollobás–Erdős conjecture on k-rails proved for k = 5 in 3-connected graphs (Theorem 3) and disproved for every k at least 5 by the lower bound f_k(n) > (k(k−1)−2)/(2k−3) (n−k) for infinitely many n (Corollary 2), with a degree condition for k-rails (Theorem 2).

spencer_1971_cliques_graphs/: Spencer's 1971 note answering Erdős's question on the maximum number g(n) of different sizes of cliques (maximal complete subgraphs) in a graph on n vertices: for every N > 33000, g(N) ≥ N − log_2 N − 4, from an explicit graph whose clique sizes run through every value from 3 to about N − log_2 N; with Moon and Moser's upper bound this is g(n) = n − log_2 n + O(1), the disproof of the conjectured iterated-logarithm term of Problem 927.

sudakov_2008_cycle_lengths_sparse_graphs/: Proves Erdos's conjecture that a graph of average degree d and girth g has at least order d^{floor((g-1)/2)} distinct cycle lengths.

sudakov_2022_extremal_number_tight_cycles/: Shows an r-uniform hypergraph on n vertices with no tight cycle has at most n^{r-1+o(1)} edges, nearly optimal.

tashkinov_1982_regular_subgraphs_regular_graphs/: Tashkinov's 1982 Doklady note proving the Berge-Sauer conjecture that every 4-regular graph has a 3-regular subgraph, and that every r-regular graph with r at least 3 has one, answering the question Erdős asked in 1981.

thomassen_1974_minimal_condition_implying_special_k4_subdivision_graph/: Thomassen's 1974 proof, for n at least 3, of Erdős's 1967 suggestion that every graph with n vertices and at least 2n−2 edges contains a cycle and a vertex off the cycle joined to at least three of its vertices (property p, a special K_4-subdivision), with the characterization of the graphs with 2n−3 edges and no such configuration as the (K_3, K_{3,3})-cockades, and the corollary reproving Dirac's theorem on subdivisions of K_4.

tuza_1990_covering_all_cliques_graph/: Bounds the clique-transversal number of chordal graphs by n/2, and by n/3 when every edge lies in a triangle, by n/k for strongly chordal and n/4 for split graphs when every edge lies in a clique of that order, with split counterexamples for every k >= 5.

verstraete_2004_number_sets_cycle_lengths/: Proves Erdos's conjecture that the number of cycle sets on {1,...,n}, the sets of cycle lengths realized by graphs on n vertices, is o(2^n), in the form o(2^{n-n^c}) for an absolute constant c > 0.

verstraete_2005_unavoidable_cycle_lengths_graphs/: Proves Erdos's conjecture that some set of integers of density zero is unavoidable: every graph of average degree at least ten has a cycle whose length lies in a prescribed set S with at most O(n^0.99) elements up to n.

wagon_1980_bound_chromatic_number_graphs_without_certain_induced_subgraphs/: Wagon's 1980 note bounding the chromatic number of a graph with no induced 2K_2 (no two independent edges) by C(ω(G)+1, 2), a polynomial in the clique number, with the generalization χ(G) ≤ f_n(ω(G)) for graphs with no induced n·K_2; the source of d(t,2) ≤ C(t,2)+1 for Problem 1111.

wang_2010_proof_erdos_faudree_conjecture_quadrilaterals/: Wang's 2010 proof of the Erdős–Faudree conjecture on quadrilaterals: Theorem B, every graph of order 4k with minimum degree at least 2k contains k disjoint cycles of length 4, proved by contradiction from an extremal chain of a triangle and k − 1 disjoint four-cycles through seven claims and a 42-page case analysis.

wang_zhu_2010_unimodality_independence_polynomials_some_graphs/: Factors independence polynomials of graphs built by attaching a rooted graph at each vertex of a path, proving log-concavity for vertebrated trees and real-rootedness for concatenations of claw-free graphs and for the graphs H_n.

wigderson_2022_erdossimonovits_compactness_conjecture_needs_more_assumptions/: Records a counterexample to the unrestricted Erdos-Simonovits compactness question and a proposed restriction excluding every forest member.

wolfovitz_2013_k_4_free_graphs_without_large_induced_triangle_free_subgraphs/: Wolfovitz's 2013 upper bound on the Erdős–Rogers function f_{3,4}(n), the largest order of a triangle-free induced subgraph forced in every K_4-free graph on n vertices: f_{3,4}(n) ≤ n^{1/2} (ln n)^{120} for all large n, by a random union of tripartite graphs on the lines of a projective plane made K_4-free by a variant of the K_4-free process; with the known lower bounds, ln f_{3,4}(n) = 0.5 ln n + O(ln ln n).

woodall_1972_sufficient_conditions_circuits_graphs/: Woodall's 1972 collection of valency and edge-count conditions for circuits of at least, or exactly, a given length; its Corollary 11.1 answers Erdős's 1969 question: a graph on n ≥ 2r + 3 vertices with at least C(n − r − 1, 2) + C(r + 2, 2) + 1 edges has a circuit of every length from 3 to n − r, sharp by two complete graphs sharing a vertex; Theorem 11 is the version with minimum valency k, and Theorem 2D a directed Ore theorem.

yi_2026_improved_upper_bound_tuza_s_conjecture/: An August 2026 four-page preprint of Yi improving Haxell's general bound for Tuza's conjecture from 66/23 to 63/22 (and to (162 + 4√3)/59) through the bound (1 + √3)ν for "2-colorable" triangle families; unrefereed, with a disclosure that generative language models were used to review and edit the manuscript only.

yosef_et_al_2021_unimodality_independence_polynomials_trees/: Reports a database computation in which every unlabeled tree on at most 20 vertices was found to have a log-concave, hence unimodal, independence polynomial, the tree case of Problem 993 through 20 vertices.

zhang_tang_2019_minimum_label_st_cut_integrality_gaps/: Zhang and Tang's integrality-gap constructions for the minimum label s-t cut problem and its two linear-programming relaxations.

zhao_2011_proof_n_2_n_2_n_2_conjecture_large_n/: Proves Loebl's conjecture for large n: a graph on n vertices in which at least n/2 vertices have degree at least n/2 contains every tree with at most n/2 edges, with the Ramsey bound 2n-2 for trees as a corollary.

---

This folder holds sources whose primary subject is Extremal and Structural Graph Theory.

Sources with other primary subjects

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

• csizmadia_1998_independence_number_minimum_distance_graphs
  • E1066
• erdos_1982_my_favourite_problems_which_recently_have
  • E0071
  • E0746
  • E0900
  • E0902
  • E0905
  • E1033
  • E1034
• swanepoel_2002_independence_numbers_planar_contact_graphs
  • E1066
• davies_2022_ramsey_problem_triangle_free_graphs
  • E1011
• erdos_1961_graph_theory_probability
  • E0151
  • E0611
• erdos_1969_problems_results_chromatic_graph_theory
  • E0767
  • E0927
• erdos_1974_general_properties_chromatic_numbers
  • E0062
• erdos_1979_problems_results_graph_theory_combinatorial_analysis
  • E0127
  • E0426
  • E0581
  • E0794
  • E0900
• erdos_1985_problems_results_chromatic_numbers_finite_infinite_graphs
  • E1111
• erdos_1988_some_aspects_my_work_gabriel_dirac
  • E0060
  • E0905
• erdos_1995_problems_combinatorial_set_theory
  • E0062
• janzer_2025_chromatic_number_regular_subgraphs
  • E0585
  • E0641
• jensen_toft_2001_25_pretty_graph_colouring_problems
  • E0062
• liu_2020_solution_erdos_hajnal_s_odd_cycle
  • E0064
  • E0065
  • E0072
• erdos_1938_sequences_integers_no_one_which_divides
  • E0572
  • E0714
  • E0765
• erdos_1969_applications_graph_theory_number_theory
  • E0712
  • E0714
  • E0794
• erdos_1997_some_old_new_problems_various_branches_combinatorics
  • E0127
  • E0133
  • E0134
  • E0136
• erdos_1961_unsolved_problems
  • E0500
• various_1999_some_pauls_favorite_problems
  • E1155
  • E1157
  • E1158
• ajtai_1980_note_ramsey_numbers
  • E0151
  • E0610
  • E0802
• alon_1999_norm_graphs_variations_applications
  • E0714
• davoodi_2026_asymptotic_version_erdos_sos_conjecture_beyond
  • E0548
• erdos_1975_problems_results_finite_infinite_graphs
  • E0182
  • E0548
  • E0581
  • E0746
  • E0900
• erdos_1979_some_old_new_problems_various_branches_combinatorics
  • E1080
• erdos_1983_more_results_ramsey_turan_type_problems
  • E0533
  • E0579
• erdos_1993_ramsey_size_linear_graphs
  • E0576
• erdos_1993_turan_ramsey_theorems_simple_asymptotically_extremal
  • E0533
• erdos_1996_some_my_favourite_problems_cycles_colourings
  • E0084
• erdos_1997_some_my_favorite_problems_results
  • E0146
  • E0147
• erdos_1997_some_recent_problems_results_graph_theory
  • E0608
  • E0642
• fizpontiveros_2020_triangle_free_process_ramsey_number
  • E0619
• fox_2008_induced_ramsey_type_theorems
  • E0061
• fox_2012_problem_erdos_rothschild_edges_triangles
  • E0905
• hefty_2025_improving_just_two_bites
  • E1011
• kim_1995_ramsey_number_has_order_magnitude
  • E0151
  • E0610
• mattheus_2023_asymptotics_r_4_t
  • E0802
• openai_2026_ten_advances_mathematics_theoretical_computer_science
  • E0113
  • E0146
  • E0147
  • E0180
  • E0575
• shearer_1983_note_independence_number_triangle_free_graphs
  • E0802
• sudakov_2003_few_remarks_ramsey_turan_type_problems
  • E0533
  • E0579
• wu_2015_ramsey_numbers_c_4_versus_wheels_stars
  • E0765
• conlon_2016_short_proofs_extremal_results_ii
  • E1008
• erdos_1981_combinatorial_problems_which_i_would_most
  • E0182
  • E0184
  • E0500
  • E0571
  • E0576
  • E0712
  • E0714
  • E0715
  • E0717
  • E0718
  • E0742
  • E0743
  • E0745
  • E0746
• erdos_1987_problems_finite_infinite_graphs
  • E0062
  • E0600
• komjath_2002_finite_subgraphs_uncountably_chromatic_graphs
  • E0062
• soukup_2015_open_problems_around_uncountable_graphs
  • E0062