×

Monochromatic paths in infinite coloured graphs. (English) Zbl 0566.05031

Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, No. 1, 359-369 (1984).
[For the entire collection see Zbl 0559.00001.]
Given two graphs G and H, and a natural number n, the notation \(G\to (H)^ 2_ n\) means, that in every edge-colouring of G, using n colours, there exists a nonchromatic subgraph, isomorphic to H. Let k be an arbitrary cardinal number and \(P_{\omega}\) the one-way infinite path. The aim of the present paper is to establish some properties of the graphs satisfying the partition relation \(G\to (P_{\omega})^ 2_ n\), for some fixed \(n<\omega\), e.g.: is it true, that if \(| V(G)| \leq k\) and \(G\to (P_{\omega})^ 2_ n\), then \(G\supseteq K_{p,q} ?\)
Thus it is proved among others, that if G is a countable graph and \(G\to (P_{\omega})^ 2_ n\), then \(G\supseteq K_{[n/2],\omega}\), and there does not exist a countable \(K_{2,2}\)-free graph \(G_ 0\), such that every countable \(K_{2,2}\)-free graph is isomorphic to a (not necessarily induced) subgraph of \(G_ 0\).
Reviewer: I.Tomescu

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C55 Generalized Ramsey theory

Citations:

Zbl 0559.00001