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

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

作　　者：刘瑶 LIU Yao(Center for Applied Mathematics,Tianjin University,Tianjin 300072,China)

机构地区：[1]天津大学应用数学中心,天津300072

出　　处：《运筹学学报》2021年第2期115-126,共12页Operations Research Transactions

基　　金：国家自然科学基金(No.11601380)。

摘　　要：给定两个非负整数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。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 x’(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.

关 键 词：强边着色 (s t)-松弛强边着色 最大平均度 平面图 围长 

分 类 号：O157.5[理学—数学]