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

Equitable Edge Coloring of Outer-1-Planar Graphs

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

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.