English

运筹学学报 ›› 2021, Vol. 25 ›› Issue (2): 115-126.doi: 10.15960/j.cnki.issn.1007-6093.2021.02.009

•   • 上一篇    下一篇

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

刘瑶1,*()   

  1. 1. 天津大学应用数学中心, 天津 300072
  • 收稿日期:2017-09-18 出版日期:2021-06-15 发布日期:2021-05-06
  • 通讯作者: 刘瑶 E-mail:liuyao@tju.edu.cn
  • 作者简介:刘瑶 E-mail: liuyao@tju.edu.cn
  • 基金资助:
    国家自然科学基金(11601380)

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

Yao LIU1,*()   

  1. 1. Center for Applied Mathematics, Tianjin University, Tianjin 300072, China
  • Received:2017-09-18 Online:2021-06-15 Published:2021-05-06
  • Contact: Yao LIU E-mail:liuyao@tju.edu.cn

RichHTML

8

PDF

122

摘要：

给定两个非负整数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)-松弛强边着色, 最大平均度, 平面图, 围长

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

中图分类号: