×

Coloring of universal graphs. (English) Zbl 0589.05053

From the text: ”J. Folkman [SIAM J. Appl. Math. 18, 19-24 (1970; Zbl 0193.531)] proved the following statement: To every finite graph G and every positive integer r there exists a graph H with \(cl(H)=cl(G)\) and such that whenever the set of vertices is partitioned into r classes \(C_ 1,C_ 2,...,C_ r\) then there exists \(i\leq r\) and some vertices in \(C_ i\) spanning a subgraph isomorphic to G. Here we consider two different extensions of Folkman’s result, both to infinite graphs. First we show that Folkman’s result remains valid if either r or cl(G) are finite. The second generalization concerns universal graphs: Let \(V_ k\) be a universal countable \(K_ k\)-free graph. Answering a question of A. Hajnal we show that for any coloring of the points of the countably universal triangle free graph \(V_ 3\) by finitely many colors we can always find a monochromatic copy of \(V_ 3\). We conjecture that the statement remains valid for \(k>3.''\)
Reviewer: I.Tomescu

MSC:

05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0193.531
Full Text: DOI

References:

[1] Cameron, P.J.: Cyclic automorphism of a countable graph and random sum-free sets. Graphs and Combinatorics1, 129–135 (1985) · Zbl 0574.05041 · doi:10.1007/BF02582937
[2] Folkman, J.: Graphs with monochromatic complete subgraphs in every edge coloring. SIAM J. Appl. Math.18, 115–124 (1970) · Zbl 0193.53103 · doi:10.1137/0118004
[3] Hajnal, A.: Proof of a conjecture of S. Rusziewicz. Fundam. Math.50, 123–128 (1961/62)
[4] Henson, C.W.: A family of countable homogenous graphs. Pacific J. Math.38, 69–83 (1971) · Zbl 0204.24103
[5] Lachlan, A.H., Woodrow, R.E.: Countable homogenous undirected graphs. Trans. Amer. Math. Soc.262, 51–94 (1980) · Zbl 0471.03025 · doi:10.1090/S0002-9947-1980-0583847-2
[6] Nešetril, J., Rödl, V.: Partition of vertices. CMUC 17,1, 85–95 (1976)
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.