The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\) (Q1078192)

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\).