Edge‐face coloring of plane graphs with maximum degree nine |
| |
| Authors: | Jean‐Sébastien Sereni Matěj Stehlík |
| |
| Affiliation: | 1. CNRS (Liafa, Université Denis Diderot) Paris, France;2. Department of Applied Mathematics (KAM) Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic;3. Liafa, Université Denis Diderot (Paris 7) Paris, France |
| |
| Abstract: | An edge‐face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ?10 can be edge‐face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332‐346, 2011 |
| |
| Keywords: | graph coloring plane graph edge‐face coloring |
|
|
