Edge-Face Coloring of Plane Graphs with Maximum Degree NineReport as inadecuate

Edge-Face Coloring of Plane Graphs with Maximum Degree Nine - Download this document for free, or read online. Document in PDF available to download.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 2 KAM - Department of Applied Mathematics KAM 3 G-SCOP OC - OC G-SCOP - Laboratoire des sciences pour la conception, l-optimisation et la production

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 1281-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.

Keywords : edge-face coloring graph coloring plane graph

Author: Jean-Sébastien Sereni - Matej Stehlík -

Source: https://hal.archives-ouvertes.fr/


Related documents