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

展开
  • 1. 天津大学应用数学中心, 天津 300072
刘瑶 E-mail: liuyao@tju.edu.cn

收稿日期: 2017-09-18

  网络出版日期: 2021-05-06

基金资助

国家自然科学基金(11601380)

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

摘要

给定两个非负整数st,图G的(st)-松弛强k边着色可表示为映射cE(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(st)-松弛强边着色指数,记作χ'(st)(G),表示使得图G有(st)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'(1,0)(G)≤3Δ-1。

本文引用格式

刘瑶 . 带松弛条件的图的强边着色[J]. 运筹学学报, 2021 , 25(2) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.009

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.

参考文献

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.
文章导航

/