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

作者：Xu Baogang^*

来源：European Journal of Combinatorics, 2007, 28(4): 1270-1275.

DOI：10.1016/j.ejc.2006.01.012

A graph G is called circular super-critical if chi(c)(G \ u) < chi(c)(G) - 1 for every vertex it of G. 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.

• 出版日期2007-5
• 单位南京师范大学