The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
type: Item
instance of: scholarly article
title: The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
zbMATH Open document ID: 0596.05028
DOI: 10.1016/0012-365X(86)90142-1
author: H. A. Kierstead
author: James H. Schmerl
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The authors call a graph G linear if G induces neither \(K_{1,3}\) nor \(K_ 5-e\). Denote by \(\Delta\) (G) the maximal degree of G and by \(\omega\) (G) the clique number of G. The main result is that if G is linear and \(\Delta\) (G)\(\leq 2\omega (G)-5\) then \(\chi (G)=\omega (G)\). It is also shown that for each \(k\geq 4\) there exists a linear graph G such that \(\omega (G)=k\), \(\Delta (G)=2k-3\) and \(\chi (G)=k+1\).
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3959457
zbMATH Keywords: chromatic number
zbMATH Keywords: maximal degree
zbMATH Keywords: clique number
zbMATH Keywords: linear graph
MaRDI profile type: Publication
cites work: On edge-colorings of graphs.
cites work: Q5570136
cites work: Improvement on Brooks' chromatic bound for a class of graphs
cites work: On the chromatic index of multigraphs without large triangles
cites work: Some applications of Vizing's theorem to vertex colorings of graphs
description: scientific article; zbMATH DE number 3959457