Chromatically optimal rigid graphs (Q1123199): Difference between revisions

All graphs considered in this paper are simple. Such a graph G is rigid if the identity map i is the only homomorphism from G into G, that is, i is the only map f from V(G) into itself such that if two vertices x and y are adjacent in G, then so are their images, f(x) and f(y). \textit{L. Babai} and \textit{J. Nešetřil} [Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 53-60 (1978; Zbl 0407.05038)] proved that every graph G, finite or infinite, is an induced subgraph of a rigid graph H. Now let k be a finite or infinite cardinal and suppose that the chromatic number \(\chi\) (G) of G is k. If G has the complete graph \(K_ k\) as an induced subgraph, then clearly \(\chi\) (H) exceeds k. This paper proves that the converse of this also holds. Hence a k- chromatic graph G is an induced subgraph of a k-chromatic rigid graph H if and only if G does not have \(K_ k\) as an induced subgraph. This theorem solves a problem of \textit{L. Babai} and \textit{J. Nešetřil} [Ann. Discrete Math. 15, 55-61 (1982; Zbl 0502.05052)]. The authors also show that their result can be strengthened when k is finite by adding the condition that H has the same girth as G.