×

On graphs of Ramsey type. (English) Zbl 0333.05120

Let \(F\) be a graph and \({\mathfrak G}\) and \({\mathfrak H}\) sets of graphs. (All graphs will be finite and simple.) A colouring of \(F\) will be a sequence of subgraphs of \(H\) — each having the same vertex-set as \(F\) — such that their edge-sets form a disjoint partition of the edge-set of \(F\). \(F \to ({\mathfrak G},{\mathfrak H})\) means that in any 2-colouring of \(F\) either the first part contains a subgraph isomorphic to a member of \({\mathfrak G}\), or the second part contains a subgraph isomorphic to a member of \({\mathfrak H}\). When \({\mathfrak G}={\mathfrak H}\), the notation is simplified to \(F \to {\mathfrak G}\). When \({\mathfrak G}\) or \({\mathfrak H}\) contain but a single graph, the notation is adjusted so that the name of the unique member replaces the name of the set. For any graph \(G\), \(\kappa (G)\) denotes the connectivity of \(G\); for any positive integer \(m\), \(mG\) denotes the disjoint union of \(m\) copies of \(G\). The set of homomorphic images of \(G\) is denoted by \(\hom G\). The direct product \(G \times H\) of two graphs \(G\) and \(H\) is the graph with vertex-set \(V(G) \times V(H)\), otherwise known as the conjunction. The chromatic Ramsey number \(r_c({\mathfrak G},{\mathfrak H})\) is the least integer \(m\) for which there exists a graph \(F\) such that \(F \to ({\mathfrak G},{\mathfrak H})\) and \(\chi (F)=m\); the Ramsey number \(r({\mathfrak G},{\mathfrak H})\) is the least integer \(n\) such that \(K_r \to ({\mathfrak G},{\mathfrak H})\). Theorem 1: For any classes \({\mathfrak G}\) and \({\mathfrak H}\), \(r_c({\mathfrak G},{\mathfrak H})=r(\hom {\mathfrak G}, \hom {\mathfrak H})\). Theorem 2: Let \(G\) and \(H\) be graphs of chromatic number \(r\), and suppose that every vertex of \(H\) is contained in a complete \((r-1)\)-graph. Then \(G \times H\) has chromatic number \(r\). Two conjectures are stated: Conjecture 1: \(\min r_c(G)=(r-1)^2+1\), where the minimum is taken over all \(r\)-chromatic graphs. Conjecture 2: \(\chi (G \times H)= \min (\chi (G), \chi (H))\). (A weakened version of Conjecture 2 follows from Theorem 2. The truth of Conjecture 2 would imply that of Conjecture 1.) Theorem 3: Conjecture 1 is valid for \(r=4\). Define \(\delta (F)\) and \(\Delta (F)\) to be the minimum and maximum degrees of vertices of \(F\). \(F\) is \((G,H)\)-irreducible if \(F \to (G,H)\) but no proper subgraph of \(F\) has this property. Theorem 4: \(2^{r/2} \leq \min \Delta (G) \leq r(K_r)-1\), where the minimum is taken over all \(G\) for which \(G \to K_r\). Theorem 5: \(\min \delta (G)=(r-1)(s-1)\), where the minimum is taken over all \((K_r,K_s)\)-irreducible graphs. Theorem 6: If \(r,s \geq 3\), there are infinitely many non-isomorphic \((K_r,K_s)\)-irreducible graphs. Theorem 7: If \(r,s \geq 3\), then there exists \((K_r,K_s)\)-irreducible graphs with arbitrarily large \(\Delta\). Theorem 8: If \(r,s \geq 3\), then \(\min K(G)=2\) or 3 according as \(r \neq s\) or \(r=s\), where the minimum is taken over all \((K_r,K_s)\)-irreducible graphs \(G\). Theorem 9: A necessary and sufficient condition that \(G \to K_{1,n}\) is that \(\Delta (G) \geq 2n-1\), or, if \(n\) is even, that \(G\) has a component which is regular of degree \(2n-2\) and which has an odd number of vertices. Theorem 10: \(G \to 2K_2\) if and only if \(G\) contains three disjoint edges or a 5-cycle. Theorem 11: For any positive integers \(m\) and \(n\), the number of \((mK_2,nK_2)\)-irreducible graphs is finite.
Reviewer: W.G.Brown

MSC:

05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite