The Entire Coloring of Series-Parallel Graphs
Jian-liangWu, Yu-liangWu · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2005
The entire chromatic number xvef (G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color.Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K4. It is proved in this paper that xvef(G)≤max{8, △(G) + 2} and xvef(G) =△+1 if G is 2-connected and △(G)≥6.