tailieunhanh - Báo cáo toán học: "Circular degree choosability"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Circular degree choosability. | Circular degree choosability Serguei Norine Xuding Zhu y Submitted Dec 19 2007 Accepted Jul 27 2008 Published Aug 4 2008 Mathematics Subject Classification 05C15 Abstract We extend a characterization of degree-choosable graphs due to Borodin 1 and Erdos Rubin and Taylor 2 to circular list-colorings. 1 Introduction Let G V G E G be a graph. A list assignment L for G is a mapping which assigns to each vertex v of G a set of non-negative integers L v . An L-coloring of G is a proper coloring c of G such that c v 2 L v for every v 2 V G . A graph G is degree-choosable if G admits an L-coloring for every list assignment L such that L v deg v for all v 2 V G . Borodin 1 and Erdos Rubin and Taylor 2 characterized degree-choosable graphs as follows. Theorem 1. A graph G is not degree-choosable if and only if each of the blocks of G is a clique or an odd cycle i. e. G is a Gallai tree . In this paper we prove an analogue of Theorem 1 for circular colorings. Informally a circular coloring is a coloring of the vertices of the graph by points of a possibly discrete circle such that the circular distance between the colors assigned to adjacent vertices of the graph is bounded from below. Circular colorings have attracted considerable attention over the last decade see 9 for a survey of the subject . Circular version of list-colorings has been recently introduced by Mohar 4 and Zhu 8 and has been since studied in 3 5 6 7 among others. Let us now formally present the relevant definitions and notation. Let p be a positive integer. For an integer a we denote by a p the remainder of a modulo p. Define Sp as 0 1 . p 1g. For a b 2 Sp the interval a b p is defined as a b p a a 1 a 2 bg Department of Mathematics Princeton University Princeton NJ 08540-1000. Partially supported by NSF grants DMS-0200595 and DMS-0701033. yDepartment of Applied Mathematics National Sun Yat-sen University Kaohsiung Taiwan 80424 and National Center for Theoretical Sciences. Partially supported by National .