Chromatically optimal rigid graphs
type: Item
instance of: scholarly article
title: Chromatically optimal rigid graphs
zbMATH Open document ID: 0677.05031
DOI: 10.1016/0095-8956(89)90039-7
author: J. Nešetřil
author: Vojtěch Rödl
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4108793
zbMATH Keywords: chromatic number
zbMATH Keywords: rigid graph
reviewed by: James Oxley
MaRDI profile type: Publication
full work available at URL: 0095-8956(89)90039-7
OpenAlex ID: W2039470646
cites work: Q4193488
cites work: High Chromatic Rigid Graphs II
cites work: Every finite graph is a full subgraph of a rigid graph
cites work: On chromatic number of graphs and set-systems
cites work: Q4087192
cites work: Symmetric relations (undirected graphs) with given semigroups
cites work: Universal graphs without large bipartite subgraphs
cites work: On a technique for representing semigroups as endomorphism semigroups of graphs with given properties
cites work: Q3887505
cites work: Q3939845
cites work: Q3208855
cites work: Q5527830
cites work: Universal graphs and universal functions
description: scientific article; zbMATH DE number 4108793