|
|
- 2015
一类平面图的强边染色
|
Abstract:
摘要： 图G的强边染色是指对图G的边进行染色,使得距离不超过2的任意两条边染不同的颜色. 任何一个平面图都可用4Δ+4种颜色进行强边染色. 证明了当平面图没有k-圈(4≤k≤10)且3-圈不相交时(即每个顶点至多关联一个3-圈), 必定存在一个3Δ+1种颜色的强边染色.
Abstract: A strong edge coloring of a graph G is an assignment of colors to the edges of the graph such that any two edges at distance at most 2 receive distinct colors. It is known that every planar graph has a strong edge-coloring with at most 4Δ+4 colors. It is proved that planar graph G has a strong edge-coloring with at most 3Δ+1 colors if G has no k-cycles with 4≤k≤10 and no intersecting 3-cycles (that is, every vertex is incident with at most one cycle of length 3)
| [1] | ANDERSEN L D. The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108:231-252. |
| [2] | FAUDREE R J, GYSRFAS A, SCHELP R H, et al. The strong chromatic index of graphs[J]. Ars Combin, 1990, 29B:205-211. |
| [3] | BENSMAIL J, HARUTYUNYAN A, HOCQUARD H, et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179:229-234. |
| [4] | HORáK P, HE Qing, TROTTER W T. Induced matchings in cubic graphs[J]. Graph Theory, 1993, 17(2):151-160. |
| [5] | CRANSTON D. Strong edge-coloring graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306:2772-2778. |
| [6] | BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan, 1976. |
| [7] | BORODIN O V, IVANOVA A O. Precise upper bound for the strong edge chromatic number of sparse planar graphs[J]. Discuss Math Graph Theory, 2013, 33:759-770. |
| [8] | MONTASSIER M, PêCHER A, RASPAUD A. Strong chromatic index of planar graphs with large girth[J]. Graph Theory and Applications, CRM Series, 2013, 16:265-270. |
| [9] | HUDáK D, LU?AR B, SOTáK R, et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324:41-49. |
