Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2002-05 May 2002

Abstract

This paper is a continuation of Part I: Triangulations, LSE-CDAM-2002-04.

Given a plane graph, a k-star at u is a set of k vertices w ith a common neighbour u; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have the same end vertices and the edges of the paths form consecutive edges (in the natural order in the plane graph) around the two end vertices. We first prove a theorem on the structure of plane graphs in terms of stars and bunches. The result states that a plane graph contains a (d-1)-star centred at a vertex of degree and the sum of the degrees of the vertices in the star is bounded, or there exists a large bunch. This structural result is used to prove a best possible upper bound on the minimum degree of the square of a planar graph, and hence on a best possible bound for the number of colours needed in a greedy colouring of it. In particular, we prove that for a planar graph G with maximum degree the chromatic number of the square of G is at most . This improves existing bounds on the chromatic number of the square of a planar graph.

A PDF file (790 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-2002-05, 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@maths.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