A note on a conjecture of Dirac (Q1850068)

A graph \(G\) is said to be vertex \(k\)-critical if \(\chi(G)=k\) and \(\chi(G-v)=k-1\) for every vertex \(v\in V(G)\). An edge \(e\in E(G)\) is called a critical edge of \(G\) whenever \(\chi(G-e)=\chi(G)-1\). In 1970, Dirac conjectured that for every integer \(k\geq 4\), there exists a vertex \(k\)-critical graph which contains no critical edges. The paper contains two constructions of families of circulant graphs that belong to the class of so-called \((\alpha,\omega)\)-graphs (\(\alpha\) and \(\omega\) are the independence number and the clique number of a graph respectively). The constructed families imply that Dirac's conjecture holds whenever \(k-1\) is no prime. The author remarks that Jensen has independently confirmed Dirac's conjecture for all \(k\geq 5\). The case \(k=4\) is still open.