Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (24): 37-40.DOI: 10.3778/j.issn.1002-8331.1812-0190

Previous Articles     Next Articles

Equitable Edge Coloring of Outer-1-Planar Graphs

LI Yan, ZHANG Xin   

  1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
  • Online:2019-12-15 Published:2019-12-11

外1-平面图的均匀边染色

李艳,张欣   

  1. 西安电子科技大学 数学与统计学院,西安 710071

Abstract: An [s]-equitable edge-[k]-coloringof a graph [G] is an edge coloring of [G] using [k] colors so that the sizes of any two color classes incident with any fixed vertex of [G] differ by at most [s]. The [s]-equitable edge chromatic threshold of [G] is the smallest [k] such that [G] has an [s]-equitable edge-[t]-colorings for integer [t] that is no less than [k]. It is proved that the 1-equitable edge chromatic threshold of any outer-1-planar graph is at most 5, the 1-equitable edge chromatic threshold of any outer-1-planar graph without adjacent triangles is at most 4, and the 2-equitable edge chromatic threshold of any outer-1-planar graph is exactly 1.

Key words: equitable edge coloring, equitable edge chromatic threshold, outer-1-planar graph

摘要: 图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。

关键词: 均匀边染色, 均匀边色数阈值, 外1-平面图