(1, 0)-Relaxed strong edge list coloring of planar graphs with girth 6

被引:0
作者
Lin, Kai [1 ]
Chen, Min [1 ]
Chen, Dong [2 ]
机构
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
[2] Zhejiang Normal Univ, Xingzhi Coll, Jinhua 321004, Zhejiang, Peoples R China
关键词
Planar graphs; strong coloring; (s; t)-relaxed strong edge list coloring; girth; STRONG CHROMATIC INDEX;
D O I
10.1142/S1793830919500642
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph. An (s, t)-relaxed strong edge k-coloring is a mapping pi : E(G) -> {1, 2, ..., 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 assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by chi((s,t))'(G), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. G is called (s, t)-relaxed strong edge L-colorable if for a given list assignment L = {L(e) vertical bar e is an element of E(G)}, there exists an (s, t)-relaxed strong edge coloring pi of G such that pi(e) is an element of L(e) for all e is an element of E(G). If G is (s, t)-relaxed strong edge L-colorable for any list assignment with vertical bar L(e)vertical bar = k for all e is an element of E(G), then G is said to be (s, t)-relaxed strong edge k-choosable. The (s, t)-relaxed strong list chromatic index, denoted by ch((s,t))'(G), is defined to be the smallest integer k such that G is (s, t)-relaxed strong edge k-choosable. In this paper, we prove that every planar graph G with girth 6 satisfies that ch((1,0))'(G) <= 3 Delta(G) - 1. This strengthens a result which says that every planar graph G with girth 7 and Delta (G) >= 4 satisfies that chi((1,0))'(G) <= 3 Delta(G) - 1.
引用
收藏
页数:11
相关论文
共 14 条
  • [1] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10
    ANDERSEN, LD
    [J]. DISCRETE MATHEMATICS, 1992, 108 (1-3) : 231 - 252
  • [2] Strong edge-colouring of sparse planar graphs
    Bensmail, Julien
    Harutyunyan, Ararat
    Hocquard, Herve
    Valicov, Petru
    [J]. DISCRETE APPLIED MATHEMATICS, 2014, 179 : 229 - 234
  • [3] A Stronger Bound for the Strong Chromatic Index
    Bruhn, Henning
    Joos, Felix
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (01) : 21 - 43
  • [4] Strong list-chromatic index of subcubic graphs
    Dai, Tianjiao
    Wang, Guanghui
    Yang, Donglei
    Yu, Gexin
    [J]. DISCRETE MATHEMATICS, 2018, 341 (12) : 3434 - 3440
  • [5] Erdos P., 1989, IRREGULARITIES PARTI, P161, DOI https://doi.org/
  • [6] FAUDREE RJ, 1990, ARS COMBINATORIA, V29B, P205
  • [7] Fouquet J.L., 1984, PROGR GRAPH THEORY, P247
  • [8] Fouquet J. L., 1982, PROGR GRAPH THEORY, P247
  • [9] Semistrong edge coloring of graphs
    Gyárfás, A
    Hubenko, A
    [J]. JOURNAL OF GRAPH THEORY, 2005, 49 (01) : 39 - 47
  • [10] On (s, t)-relaxed strong edge-coloring of graphs
    He, Dan
    Lin, Wensong
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (02) : 609 - 625