CDAM: Computational, Discrete and Applicable Mathematics@LSE

CDAM Research Report, LSE-CDAM-2008-09

July 2008

List Coloring Squares of Planar Graphs

Frédéric Havet, Jan van den Heuvel, Colin McDiarmid and Bruce Reed

In 1977, Wegner conjectured that the chromatic number of the square of every planar graph G with maximum degree Δ ≥ 8 is at most ⌊3Δ⁄2⌋ + 1. We show that it is at most 3Δ⁄2(1+o(1)), and indeed this is true for the list chromatic number and for more general classes of graphs.

A PDF file (352 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-2008-09, 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 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		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 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk