CIRCULAR CONSECUTIVE CHOOSABILITY OF GRAPHS
CIRCULAR CONSECUTIVE CHOOSABILITY OF GRAPHS
复制标题
DOI：
10.11650/tjm.12.2008.623
复制
发表时间：
2008-01
影响因子：
0.4
通讯作者：
Wensong Lin;Daqing Yang;Chung-Ying Yang;Xuding Zhu
中科院分区：
文献类型：
--
作者：
Wensong Lin;Daqing Yang;Chung-Ying Yang;Xuding Zhu
本文研究了图的列表圆形着色问题，其中每个顶点的颜色列表是一个圆的区间。{\em}$G$的循环连续可选择性$ch_{cc}(G)$被定义为最小的$t$，使得对于任何长度为$r \geq \chi_c(G)$的圆$S(r)$，如果$G$的每个顶点$x$被分配一个长度为$t$的$S(r)$的区间$L(x)$，则存在一个$G$的循环$r$ -着色$f$，使得$f(x) \in L(x)$。我们证明了对于任意有限图$G$, $\chi(G)-1 \leq ch_{cc}(G) < 2 \chi_c(G)$。我们确定了完全图、树、偶环和平衡完全二部图的$ch_{cc}(G)$的值。对于一些其他类型的图，给出了$ch_{cc}(G)$的上界和下界。
This paper considers list circular colouring of graphs in which the colour list assigned to each vertex is an interval of a circle. The {\em circular consecutive choosability} $ch_{cc}(G)$ of $G$ is defined to be the least $t$ such that for any circle $S(r)$ of length $r \geq \chi_c(G)$, if each vertex $x$ of $G$ is assigned an interval $L(x)$ of $S(r)$ of length $t$, then there is a circular $r$-colouring $f$ of $G$ such that $f(x) \in L(x)$. We show that for any finite graph $G$, $\chi(G)-1 \leq ch_{cc}(G) < 2 \chi_c(G)$. We determine the value of $ch_{cc}(G)$ for complete graphs, trees, even cycles and balanced complete bipartite graphs. Upper and lower bounds for $ch_{cc}(G)$ are given for some other classes of graphs.