Edge coloring of embeddable graphs and edge-face coloring of simple plane graphs
by
Rong Luo
Department of Mathematics, West Virginia University, Morgantown, WV
Coauthors: Xuechao Li, Cun-Quan Zhang

It is proved that a simple graph G which is embeddable on a surface \Sigma with Euler characteristic \chi(\Sigma) >= 0 is class one if \Delta >= 5 and g >= 4, or \Delta >= 4 and g >= 5, or \Delta >= 3 and g >= 9, or \chi(\Sigma) > 0, \Delta >= 3 and g >= 8, where \Delta,   g are the maximum degree and the girth of G, respectively.

It is also proved that \chi_ef(G) = \chi_e(G) = \Delta(G) for any 2-connected simple plane graph G with \Delta(G) >= 24 where \chi_ef (G) and \chi_e(G) are the edge-face chromatic number and the edge chromatic number of G, respectively.

Date received: April 17, 2001