中文

Operations Research Transactions >

2021 , Vol. 25 >Issue 2: 115 - 126

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.02.009

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

Expand
  • 1. Center for Applied Mathematics, Tianjin University, Tianjin 300072, China

Received date: 2017-09-18

  Online published: 2021-05-06

Fold

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

Cite this article

Yao LIU . On (1, 0)-relaxed strong edge-coloring of graphs[J]. Operations Research Transactions, 2021 , 25(2) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.009

References

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.
Options
Outlines

/

〈 〉