运筹学学报 >
2021 , Vol. 25 >Issue 2: 115 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.02.009
带松弛条件的图的强边着色
收稿日期: 2017-09-18
网络出版日期: 2021-05-06
基金资助
国家自然科学基金(11601380)
On (1, 0)-relaxed strong edge-coloring of graphs
Received date: 2017-09-18
Online published: 2021-05-06
给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'(1,0)(G)≤3Δ-1。
关键词: 强边着色; (s, t)-松弛强边着色; 最大平均度; 平面图; 围长
刘瑶 . 带松弛条件的图的强边着色[J]. 运筹学学报, 2021 , 25(2) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.009
Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is a mapping c : E(G) → [k], such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e having the color c(e). The (s, t)-relaxed strong chromatic index, denoted by χ' (s, t)(G), is the minimum number k such that G admits an (s, t)-relaxed strong k-edge-coloring. We prove that if G is a graph with mad(G) < 3 and Δ ≤ 4, then χ'(1, 0)(G) ≤ 3Δ. In addition, we prove that if G is a planar graph with Δ ≥ 4 and girth at least 7, then χ'(1, 0)(G) ≤ 3Δ - 1.
| 1 | Fouquet J L , Jolivet J L . Strong edge-colorings of graphs and applications to multi-$ k $-gons[J]. Ars Combinatoria, 1983, 16 (A): 141- 150. |
| 2 | Fouquet J L, Jolivet J L. Strong edge-coloring of cubic planar graphs, in: Progress in graph theory[M]//Progress in Graph Theory, Waterloo: Academic Press, 1984, 247–264. |
| 3 | Erd?s P . Problems and results in combinatorial analysis and graph theory[J]. Discrete Mathematics, 1988, 72 (1/2/3): 81- 92. |
| 4 | Andersen L D . The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108 (1/2/3): 231- 252. |
| 5 | Horák P , Qing H , Trotter W T . Induced matchings in cubic graphs[J]. Journal of Graph Theory, 1993, 17 (2): 151- 160. |
| 6 | Cranston D W . Strong edge-coloring of graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306 (21): 2772- 2778. |
| 7 | Molloy M , Reed B . A bound on the strong chromatic index of a graph[J]. Journal of Combinatorial Theory. Series B, 1997, 69 (2): 103- 109. |
| 8 | Bruhn H , Joos F . A stronger bound for the strong chromatic index[J]. Combinatorics, Probability and Computing, 2017, |
| 9 | Hocquard H , Montassier M , Raspaud A , Valicov P . On strong edge-colouring of subcubic graphs[J]. Discrete Applied Mathematics, 2013, 161 (16/17): 2467- 2479. |
| 10 | Hocquard H , Valicov P . Strong edge colouring of subcubic graphs[J]. Discrete Applied Mathematics, 2011, 159 (15): 1650- 1657. |
| 11 | Faudree R J , Schelp R H , Gyárfás A , et al. The strong chromatic index of graphs[J]. Ars Combinatoria, 1990, 29 (B): 205- 211. |
| 12 | Bensmail J , Harutyunyan A , Hocquard H , et al. Strong edge-colouring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179, 229- 234. |
| 13 | Hudák D , Lu?ar B , Soták R , et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324, 41- 49. |
| 14 | Ruksasakchai W , Wang T . List strong edge coloring of some classes of graphs[J]. The Australasian Journal of Combinatorics, 2017, 68, 106- 117. |
| 15 | He D , Lin W . On $ (s, t) $-relaxed strong edge-coloring of graphs[J]. Journal of Combinatorial Optimization, 2017, 33 (2): 609- 625. |
/
| 〈 |
|
〉 |