Speaker : Prof. Pan, Zhi-Shi (Tamkang University)
Title : Circular consecutive choosability of -choosable graphs
Time : 2014-03-07 (Fri) 14:00 - 15:30
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: Let denote a circle of circumference . The circular consecutive choosability of a graph is the least real number such that for any , if each vertex is assigned a closed interval of length on , then there is a circular -colouring of such that . We investigate, for a graph, the relations between its circular consecutive choosability and choosibility. It is proved that for any positive integer , if a graph is -choosable, then ; moreover, the bound is sharp for . For , it is proved that if is -choosable then , while the equality holds if and only if contains a cycle. In addition, we prove that there exist circular consecutive -choosable graphs which are not -choosable. In particular, it is shown that holds for all cycles and for with . On the other hand, we prove that holds for many generalized theta graphs.