带松弛条件的图的强边着色

doi:10.15960/j.cnki.issn.1007-6093.2021.02.009

Abstract

Abstract:

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.

Key words: strong edge-coloring, (s, t)-relaxed strong edge-coloring, maximum average degree, planar graphs, girth

CLC Number:

O157.5

Yao LIU. On (1, 0)-relaxed strong edge-coloring of graphs[J]. Operations Research Transactions, 2021, 25(2): 115-126.

References 15

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. doi: 10.1002/jgt.3190170204
6	Cranston D W . Strong edge-coloring of graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306 (21): 2772- 2778. doi: 10.1016/j.disc.2006.03.053
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. doi: 10.1006/jctb.1997.1724
8	Bruhn H , Joos F . A stronger bound for the strong chromatic index[J]. Combinatorics, Probability and Computing, 2017, doi: 10.1017/S0963548317000244
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. doi: 10.1016/j.dam.2011.06.015
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. doi: 10.1016/j.dam.2014.07.006
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. doi: 10.1016/j.disc.2014.02.002
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. doi: 10.1007/s10878-015-9983-6

[1]	LAN Yongxin, SHI Yongtang, SONG Zixia. Planar Turán number and planar anti-Ramsey number of graphs [J]. Operations Research Transactions, 2021, 25(3): 200-216.
[2]	Xiaoxia LIN. A note on quasi k-connected graphs [J]. Operations Research Transactions, 2021, 25(1): 137-140.
[3]	Min CHEN, Jianmin YANG, Hao ZHANG, Yiting WANG. Weakly entire coloring of outerplanar graphs [J]. Operations Research Transactions, 2021, 25(1): 132-136.
[4]	Jing ZHAO, Erfang SHAN, Jiagui ZHAO. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131.
[5]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[6]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[7]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[8]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[9]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[10]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[11]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[12]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[13]	MEI Ruoxing, WANG Ligong, WANG Luhua, WANG Zhanqing. Laplacian spectral characterizations of unicyclic graphs H( p, t K_{ 1, m}) [J]. Operations Research Transactions, 2015, 19(1): 57-64.
[14]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.
[15]	SUN Lin, LUO Zhaoyang. Edge colourings of embedded special graphs [J]. Operations Research Transactions, 2015, 19(1): 125-130.

On (1, 0)-relaxed strong edge-coloring of graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 15

Related Articles 15

Recommended Articles

Metrics

Comments