Premium
Polychromatic colorings of bounded degree plane graphs
Author(s) -
Horev Elad,
Krakovski Roi
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20357
Subject(s) - combinatorics , mathematics , planar graph , complete coloring , graph coloring , list coloring , edge coloring , bounded function , graph , monochromatic color , fractional coloring , discrete mathematics , degree (music) , plane (geometry) , graph power , line graph , geometry , physics , mathematical analysis , acoustics , optics
A polychromatic k ‐ coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G , one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K 4 or a subdivision of K 4 on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom