Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef(G). This paper proves that if △ ≥6, then △+ 1≤Xvef(G)≤△+ 2, and Xvef (G) = △+ 1 if and only if G has a matching M...Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef(G). This paper proves that if △ ≥6, then △+ 1≤Xvef(G)≤△+ 2, and Xvef (G) = △+ 1 if and only if G has a matching M consisting of some inner edges which covers all its vertices of maximum degree.展开更多
The entire chromatic number χ_(vef) (G) of a plane graph G is the minimalnumber of colors needed for coloring vertices, edges and faces of G such that no two adjacent orincident elements are of the same color. Let G ...The entire chromatic number χ_(vef) (G) of a plane graph G is the minimalnumber of colors needed for coloring vertices, edges and faces of G such that no two adjacent orincident elements are of the same color. Let G be a series-parallel plane graph, that is, a planegraph which contains no subgraphs homeomorphic to K 4. It is proved in this paper that χ_(vef)(G)≤ max{8, Δ(G) + 2} and χ_(vef) (G) = Δ + 1 if G is 2-connected and Δ(G) ≥ 6.展开更多
文摘Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef(G). This paper proves that if △ ≥6, then △+ 1≤Xvef(G)≤△+ 2, and Xvef (G) = △+ 1 if and only if G has a matching M consisting of some inner edges which covers all its vertices of maximum degree.
基金Supported by the National Natural Science Foundation of China (No. 10471078)the Doctoral Foundation of the Education Committee of China (No. 2004042204)
文摘The entire chromatic number χ_(vef) (G) of a plane graph G is the minimalnumber of colors needed for coloring vertices, edges and faces of G such that no two adjacent orincident elements are of the same color. Let G be a series-parallel plane graph, that is, a planegraph which contains no subgraphs homeomorphic to K 4. It is proved in this paper that χ_(vef)(G)≤ max{8, Δ(G) + 2} and χ_(vef) (G) = Δ + 1 if G is 2-connected and Δ(G) ≥ 6.