Erdos 1966 chromatic number graphs set systems

../

assertion_p73: The unproved assertion, with Problem 5.10, that every graph whose number of vertices and chromatic number both equal an infinite alpha has a triangle-free subgraph with the same two values; open in the paper.

assertion_p77: The unproved assertion that every graph with omega_1 vertices and chromatic number omega_1 contains an omega-fold connected subgraph with omega_1 vertices and chromatic number omega_1; open in the paper.

corollary_13_4: For every k >= 2, r and s there are s-circuitless k-uniform set systems of chromatic number at least r, equivalently a countable s-circuitless k-uniform system of chromatic number omega.

corollary_5_6: Uncountable coloring number forces K_{i, aleph_1} for every finite integer i.

problem_7_6: Asks whether every graph of chromatic number greater than omega contains odd circuits of every sufficiently large length; the authors announce, with the proof omitted, an affirmative answer above omega_2.

problem_7_8: Asks whether, for every graph of chromatic number omega, the reciprocals of the lengths of its circuits have infinite sum; open in the paper.

theorem_13_3: For every k >= 3 and s there are epsilon > 0 and n_0 such that for every n > n_0 some s-circuitless k-uniform set system on n points has no independent set of more than n^(1-epsilon) points.

theorem_3_1: For a set system whose members are finite sets of at least two elements, the chromatic number is at most the colouring number; graphs are the case of two-element sets.

theorem_5_11: For every infinite beta there is a graph on beta^+ vertices of colouring number beta^+ containing neither a complete bipartite graph with both parts of size beta nor any circuit of odd length.

theorem_5_5: For infinite beta, every graph of colouring number greater than beta contains a complete bipartite graph with parts of sizes beta^+ and delta, for finite delta outright and for infinite delta < beta under GCH.

theorem_5_9: Under GCH, for every infinite beta there is a graph on beta^+ vertices of chromatic number beta^+ containing neither a complete bipartite graph with both parts of size beta nor an infinite complete graph.

theorem_7_4: For every infinite beta and every integer j there is a graph with beta vertices and chromatic number beta containing no circuit of length 2i+1 for 1 <= i <= j.

theorem_7_5: Every graph of chromatic number at least omega contains circuits of length 2i+1 for infinitely many i.

theorem_7_7: A finite graph containing no circuit of length 2i+1 for any i >= j has chromatic number at most 2j, which the complete graph on 2j vertices shows is best possible.

theorem_9_1: For every finite beta >= 2, a graph all of whose finite subgraphs have colouring number at most beta has colouring number at most 2beta-2.

theorem_9_2: For every finite beta >= 2 there is a countable graph all of whose finite subgraphs have colouring number at most beta but whose colouring number exceeds 2beta-3.

---

P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61--99, DOI 10.1007/BF02020444 (MR 33 #1247; Zentralblatt 151,337). No copyright line is printed in the scan, a Rényi archive copy (pp. 1--2 and 38--39 read); this article's own publisher page was not consulted, and the Crossref record of another article in the same journal (DOI 10.1007/BF02023868, read 2026-10-02) names only Springer's text-and-data-mining terms (http://www.springer.com/tdm) and no Creative Commons license, while that article's Springer page redirected to a cookie and login wall, every other right reserved.

This long paper introduces the coloring number alongside the chromatic number and studies which subgraphs a large coloring or chromatic number forces. Theorem 3.1 shows that the chromatic number is at most the coloring number for set systems of finite sets of size at least two, graphs included. Theorem 5.5 shows that a graph of coloring number greater than an infinite beta contains a complete bipartite graph with parts of sizes beta^+ and delta, for finite delta in ZFC and for infinite delta < beta under GCH (with at most alpha(delta) vertices when delta^+ = beta), and Theorem 5.9 (under GCH) and Theorem 5.11 give graphs on beta^+ vertices of chromatic, respectively coloring, number beta^+ with no complete bipartite graph with both parts of size beta. The case beta = omega of Theorem 5.5(iii) is Corollary 5.6: a graph of coloring number greater than omega contains K_{i, aleph_1} for every finite i. Such a graph contains every even cycle, and a C_4-free graph has coloring number at most omega (p. 62). With Theorem 3.1 this gives a cycle of length 2^m for every m >= 2 in every graph of uncountable chromatic number, the case of Problem 63 recorded on its partial claim page. After Theorem 5.9 the paper poses Problem 5.10 and an unproved assertion on triangle-free subgraphs of full chromatic number (p. 73).

Section 7 turns to circuits. Theorem 7.4 gives, for every beta >= omega and every integer j, a graph with beta vertices and chromatic number beta with no circuit of length 2i+1 for 1 <= i <= j. Theorem 7.7 bounds by 2j the chromatic number of a finite graph with no circuit of length 2i+1 for any i >= j, and Theorem 7.5 derives that a graph of chromatic number at least omega has odd circuits of infinitely many lengths. Problem 7.6 asks whether chromatic number greater than omega forces odd circuits of all sufficiently large lengths; the authors announce an affirmative answer above omega_2 with the proof omitted, and note that a positive answer would follow from an unproved connectivity assertion (p. 77). Problem 7.8 asks whether the reciprocals of the circuit lengths of a graph of chromatic number omega must have infinite sum.

Sections 8--11 study a four-cardinal relation generalizing R. Rado's question whether a graph whose finite subgraphs have coloring number at most a finite beta has coloring number at most beta. Theorem 9.1 gives the bound 2beta-2 for every 2 <= beta < omega, and Theorem 9.2 shows on countable graphs that it cannot be lowered, so the answer is affirmative exactly for beta = 2, in contrast with the de Bruijn-Erdős compactness theorem for chromatic number. Section 13 generalizes Erdős's theorem on graphs of large girth and chromatic number to uniform set systems: Theorem 13.3 gives, for every k >= 3 and s and all large n, s-circuitless k-uniform systems on n points with no independent set of more than n^(1-epsilon) points, and Corollary 13.4 draws s-circuitless k-uniform systems of arbitrarily large chromatic number.

Read status: claims checked for the results with pages below, each read clause by clause on the page images with its read depth recorded on its page; no proof was checked.

Source: https://users.renyi.hu/~p_erdos/1966-07.pdf.

Bears on.

• #57: a positive answer to Problem 57 for graphs of chromatic number omega answers Problem 7.8 positively; Theorem 7.5 gives the weaker fact that the odd cycle lengths form an infinite set.
• #63: Corollary 5.6 with Theorem 3.1 gives a cycle of length 2^m for every m >= 2 in every graph of uncountable chromatic number; chromatic number aleph_0 is not covered.
• #108: Problem 108's page deduces the case k = 3 from Theorem 7.7 and compactness.
• #594: Problem 7.6 asks Problem 594's question; the paper announces, without proof, the case of chromatic number greater than omega_2.
• #740: the p. 73 assertion is the case r = 3 of Problem 740 for graphs whose number of vertices equals their chromatic number.
• #1022: Corollary 13.4 supplies the auxiliary hypergraphs of the Kostochka construction that the library applies to Problem 1022.
• #1067: the p. 77 assertion asks Problem 1067's question for graphs with aleph_1 vertices, with the paper's omega-fold connectivity.
• #1068: the site cites the paper for Problem 1068; the paper asks no question about countable infinitely connected subgraphs, and the p. 77 assertion is its nearest statement.

Other results identified.

• Theorem 7.1 (p. 76): every graph of coloring number greater than omega contains an infinite path.
• Theorem 12.1 and Problem 12.3 (pp. 93--94): an analogue of Theorem 5.5 for k-uniform set systems, and the question whether a 3-uniform system on omega_1 points of coloring number (or at least chromatic number) greater than omega must have 5 points spanning at least 4 of its triples.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.