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.展开更多
Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices o...Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of 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 ...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.
基金Project supported by the Vatural SCience Foundation of LNEC.
文摘Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.
基金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.
基金Supported by the Natural Science Foundation of China(10871205,11101245)the Natural Science Foundation of Shandong Province(BS2010SF017,ZR2001AQ005)the Young Foundation of Shandong Institute of Business and Technogy(2011QN066)
