An analogue of Dirac’s theorem on circular super-critical graphs

A graph GG is called circular super-critical if χc(G∖u)<χc(G)−1χc(G∖u)<χc(G)−1 for every vertex uu of GG. In this paper, analogous to a result of Dirac on chromatic critical graphs, a sharp lower bound on the vertex degree of circular super-critical graphs is proved. This lower bound provides a partial answer to a question of X. Zhu [The circular chromatic number of induced subgraphs, J. Combin. Theory Ser. B 92 (2004) 177–181]. Some other structural properties of circular super-critical graphs are also presented.