×

What must and what need not be contained in a graph of uncountable chromatic number? (English) Zbl 0541.05026

This paper is concerned with the subgraphs of a graph with chromatic number \(\geq \aleph_ 1\). It is known that every such graph must contain as a subgraph the complete bipartite graphs \(K_{\aleph_ 1,i}\) for each finite i (and so in particular contain a 4-cycle); on the other hand for each finite i there are graphs with chromatic number \(\aleph_ 1\) which contain no cycles of odd length \(\leq i\). (See P. Erdős and A. Hajnal [Acta Math. Acad. Sci. Hung. 17, 61-99 (1966; Zbl 0151.337)].) This paper considers two very similar graphs \(\Gamma\) and \(\Delta\), where \(\Gamma\) is the graph on vertex set \(\{a\}\cup \{x_ i,y_ i\); \(i<\omega \}\) with each \(y_ i\) joined to \(\{x_ 0,...,x_{i-1}\}\) and a joined to \(\{x_ i\); \(i<\omega \}\), and \(\Delta\) is the graph on vertex set \(\{a,b\}\cup \{x_ i,y_ i\); \(i<\omega \}\) with again each \(y_ i\) joined to \(\{x_ 0,...,x_{i- 1}\}\) and both a, b joined to \(\{x_ i\); \(i<\omega \}\). The authors show that every graph with chromatic number \(\geq \aleph_ 1\) contains a subgraph isomorphic to \(\Gamma\), but using CH they construct a graph (on \(\aleph_ 1\) vertices) with chromatic number \(\aleph_ 1\) which has no subgraph isomorphic to \(\Delta\).
Reviewer: N.H.Williams

MSC:

05C15 Coloring of graphs and hypergraphs
03E05 Other combinatorial set theory

Citations:

Zbl 0151.337
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos, Graph theory and probability,Canad. J. Math. 11 (1959), 34–38. · Zbl 0084.39602
[2] P. Erdos, F. Galvin andA. Hajnal, On set systems having large chromatic numbers and not containing prescribed subsystems,Coll. Math. Soc. János Bolyai 10,Infinite and Finite Sets, Keszthely (Hungary) 1973, 425–513.
[3] P. Erdos andA. Hajnal, On chromatic number of graphs and set-systems,Acta Math. Acad. Sci. Hung. 17 (1966), 61–99. · Zbl 0151.33701
[4] P. Erdos, A. Hajnal andS. Shelah, On some general properties of chromatic numbers,Coll. Math. Soc. János Bolyai 8,Topics in Topology, Keszthely, (Hungary) 1973, 243–255.
[5] P. Erdos andR. Rado, A construction of graphs without triangles having pre-assigned order and chromatic number,Journal of the London Math. Soc. 35 (1960), 445–448. · Zbl 0097.16402
[6] A. Hajnal andA. Máté, Set mappings, partitions and chromatic numbers,Proceedings of Bristol Logic Conference, July 1973, 67–69.
[7] P. Komjáth, A note on Hajnal–Máté graphs,Studia Sci. Math. Hung. 15 (1981), 275–278.
[8] L. Lovász, On chromatic number of graphs and set-systems,Acta Math. Acad. Sci. Hung. 19 (1969), 59–67. · Zbl 0157.55203
[9] J. Mycielski, Sur le coloriage des graphs,Colloq. Math. 3 (1955), 161–162. · Zbl 0064.17805
[10] C. Thomassen, Cycles in graphs of uncountable chromatic number,Combinatorica 3 (1983), 133–134. · Zbl 0523.05046
[11] A. A. Zykov, On some properties of linear complexes,Russian Math. Sbornik, N. S. 24 (66) (1949), 163–188.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.