組合數學研討會
主講者: 潘志實 教授 (淡江大學)
講題: Circular consecutive choosability of $k$-choosable graphs
時間: 2014-03-07 (Fri.)  14:00 - 15:30
地點: 數學所 617 研討室 (台大院區)
Abstract: Let $S(r)$ denote a circle of circumference $r$. The circular consecutive choosability $ch_{cc}(G)$ of a graph $G$ is the least real number $t$ such that for any $r \geq \chi_c(G)$, if each vertex $v$ is assigned a closed interval $L(v)$ of length $t$ on $S(r)$, then there is a circular $r$-colouring $f$ of $G$ such that $f(v) \in L(v)$. We investigate, for a graph, the relations between its circular consecutive choosability and choosibility. It is proved that for any positive integer $k$, if a graph $G$ is $k$-choosable, then $ch_{cc}(G) \le k+1-1/k$; moreover, the bound is sharp for $k \ge 3$. For $k=2$, it is proved that if $G$ is $2$-choosable then $ch_{cc}(G) \le 2$, while the equality holds if and only if $G$ contains a cycle. In addition, we prove that there exist circular consecutive $2$-choosable graphs which are not $2$-choosable. In particular, it is shown that $ch_{cc}(G)=2$ holds for all cycles and for $K_{2,n}$ with $n \geq 2$. On the other hand, we prove that $ch_{cc}(G) > 2$ holds for many generalized theta graphs.
  || Close window ||