On the chromatic number of a graph with two forbidden subgraphs
type: Item
instance of: scholarly article
title: On the chromatic number of a graph with two forbidden subgraphs
zbMATH Open document ID: 0676.05041
DOI: 10.1016/0095-8956(89)90002-6
author: Medha Dhurandhar
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: A well-known result of Vizing asserts that the edge chromatic number of a graph G equals either \(\Delta\) (G) or \(\Delta (G)+1\) when \(\Delta\) (G) is the maximum degree of G. By using Beineke's forbidden-induced-subgraph characterization of line graphs, \textit{S. A. Choudum} [Q. J. Math., Oxf. II. Ser. 28, 257-270 (1977; Zbl 0364.05023)] restated this result as follows: If G is a simple graph whose maximum clique has d(G) vertices, then \(\chi\) (G), the (vertex) chromatic number of G, is at most \(d(G)+1\) provided that G has no induced subgraph isomorphic to any of nine particular graphs. Choudum, Javdekar, and Kierstead sharpened this result by proving that the conclusion remains true when certain of the nine graphs are eliminated from the hypothesis. The best such result was proved by \textit{H. A. Kierstead} [J. Comb. Theory, Ser. B 36, 156-160 (1984; Zbl 0541.05027)] who showed that \(\chi (G)\leq | d(G)+1\) provided that G has no induced subgraph isomorphic to \(K_{1,3}\) or \(K_ 5-e\). In this paper, the author proves that the same bound on \(\chi\) (G) holds provided that G has no induced subgraph isomorphic to either \(K_{1,3}\) or the graph obtained from \(K_ 5\) by deleting two adjacent edges.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4106879
zbMATH Keywords: maximum clique size
zbMATH Keywords: forbidden subgraph
zbMATH Keywords: chromatic number
reviewed by: James Oxley
MaRDI profile type: Publication
full work available at URL: 0095-8956(89)90002-6
OpenAlex ID: W2021242070
cites work: CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
cites work: Note on Choudum's “chromatic bounds for a class of graphs”
cites work: On the chromatic index of multigraphs without large triangles
cites work: Q3115603
description: scientific article; zbMATH DE number 4106879