Article ID Journal Published Year Pages File Type
4651318 Discrete Mathematics 2006 6 Pages PDF
Abstract

The rainbowness  , rb(G)rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that n2+α1*-1⩽rb(G)⩽n-α0*+1,where α0* and α1* denote the independence number and the edge independence number, respectively, of the dual graph G*G* of G  . We also prove that if the dual graph G*G* of an n-vertex cubic 3-connected plane graph G has a perfect matching then rb(G)=34n.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,