|
|
- 2016
平面图的平方染色数的一个新上界
|
Abstract:
摘要： 令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。
Abstract: Let V(G), E(G), Δ(G) and χ(G) denote the vertex set, the edge set, the maximum degree and the chromatic number of a graph G, respectively. The square G2 of a graph G is defined such that V(G2)=V(G), and uv∈E(G2)if and only if 1≤dG(u,v)≤2. It is proved that χ(G2)≤Δ(G)+8 if G is a planar graph with Δ(G)≤6 and girth g(G)≥5
| [1] | WEGNER G. Graphs with given diameter and coloring problem[R]. Dortmund, Germany:Technical Report, University of Dortmund, 1977. |
| [2] | MOLLY M, SALAVATIPOUR M R. A bound on the chromatic number of the square of a planar graph[J]. J Combinatorial Theory: B, 2005, 94:189-213. |
| [3] | WANG Weifan, CAI L Z. Labeling planar graphs without 4-cycles with a conditionon distance two[J]. J Discrete Applied Mathematics, 2008, 156:2241-2249. |
| [4] | BORODIN O V, IVANOVA A O. 2-distance Δ+2-coloring of planar graphs with girth six and Δ(<i>G</i>)≥18[J]. Discrete Mathematics, 2009, 309:6496-6502. |
| [5] | WANG Weifan, LIH K W. Labeling planar graphs with conditions on girth and distance two[J]. SIAM J Discrete Mathematics, 2003, 17(2):264-275. |
| [6] | 徐俊明. 图论及其应用[M]. 2版. 合肥: 中国科学技术大学出版社, 2005. XU Junming. Graph theory and its applications[M]. 2nd ed. Hefei: China University of Science and Technology Press, 2005. |
| [7] | ZHU Haiyang, HOU Lifeng, CHEN Wei, et al. The <i>L(p; q)</i>-labelling of planar graphs without 4-cycles[J]. Discrete Applied Mathematics, 2014, 162:355-363. |
| [8] | CHARPENTIER C, MONTASSIER M, RASPAUD A. <i>L(p,q)</i>-labeling of sparse graphs[J]. Journal of Combinatorial Optimization, 2013, 25(4):646-660. |
| [9] | HEUVEL J V, McGUINESS S. Coloring of the square of a planar graph[J]. J Graph Theory, 2003, 42:110-124. |
