Circular Chromatic Number and Mycielski Graphs
Circular Chromatic Number and Mycielski Graphs
复制标题
DOI：
10.1007/s00493-004-0008-9
复制
发表时间：
2004
期刊：
影响因子：
1.1
通讯作者：
G. Fan
中科院分区：
文献类型：
--
作者：
G. Fan
作为图着色的自然推广，Vince 引入了图 G 的星色数，并用 χ*(G) 表示。后来朱把它称为圆色数，记为χc(G)。令χ(G)为G的色数。本文证明，如果G的补集非哈密顿，则χc(G)=χ(G)。用 M(G) 表示 G 的 Mycielski 图。递归地定义Mm(G)=M(Mm−1(G))。推测若m≤n−2，则χc(Mm(Kn))=χ(Mm(Kn))。假设G是一个有n个顶点的图。我们证明如果，则χc(M(G))=χ(M(G))。设S 为G 中n−1 度的顶点集。证明若|S|≥ 3，则χc(M(G))=χ(M(G))，若|S|≥ 5，则χc(M2(G))=χ(M2(G))，这意味着Chang、Huang、Zhu的已知结果ifn≥3，χc(M(Kn))=χ(M(Kn))，且ifn≥5，那么χc(M2(Kn))=χ(M2(Kn))。
As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graphGand denoted it byχ*(G). Later, Zhu called it circular chromatic number and denoted it byχc(G). Letχ(G) be the chromatic number ofG. In this paper, it is shown that if the complement ofGis non-hamiltonian, thenχc(G)=χ(G). Denote byM(G) the Mycielski graph ofG. Recursively defineMm(G)=M(Mm−1(G)). It was conjectured that ifm≤n−2, thenχc(Mm(Kn))=χ(Mm(Kn)). Suppose thatGis a graph on n vertices. We prove that if, thenχc(M(G))=χ(M(G)). LetSbe the set of vertices of degreen−1 inG. It is proved that if |S|≥ 3, thenχc(M(G))=χ(M(G)), and if |S|≥ 5, thenχc(M2(G))=χ(M2(G)), which implies the known results of Chang, Huang, and Zhu that ifn≥3,χc(M(Kn))=χ(M(Kn)), and ifn≥5, thenχc(M2(Kn))=χ(M2(Kn)).