Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2004-04 April 2004

Abstract

A cyclic colouring of a plane graph is a vertex colouring such that vertices incident with the same face have distinct colours. The minimum number of colours in a cyclic colouring of a graph is its cyclic chromatic number  chi^c.  Let  Delta*  be the maximum face degree of a graph. There exist plane graphs with   chi^c = floor(3 Delta*/2).  Ore and Plummer (1969) proved that  chi^c ≤ 2 Delta*,  which bound was improved to  floor(9 Delta*/5)  by Borodin, Sanders and Zhao (1999), and to  floor(5 Delta*/3)  by Sanders and Zhao (2001).
We introduce a new parameter  k*,  which is the maximum number of vertices that two faces of a graph can have in common, and prove that  chi^c ≤ max{ Delta* + 3 k* + 2, Delta* + 14, 3 k* + 6, 18 },  and if  Delta* ≥ 4  and  k* ≥ 4, , then  chi^c ≤ Delta* + 3 k* + 2.

A PDF file (200 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2004-04, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@cdam.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html