List Edge Coloring of Outer-1-planar Graphs

被引：1

作者：

Xin ZHANG

机构：

[1] SchoolofMathematicsandStatistics,XidianUniversity

来源：

ActaMathematicaeApplicataeSinica | 2020年 / 36卷 / 03期

关键词：

outerplanar graph; outer-1-planar graph; crossing distance; list edge coloring;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. It is known that the list edge chromatic number χ′l（G） of any outer-1-planar graph G with maximum degree Δ（G） ≥ 5 is exactly its maximum degree. In this paper, we prove χ′l（G） = Δ（G） for outer-1-planar graphs G with Δ（G） = 4 and with the crossing distance being at least 3.

引用

页码：737 / 752

页数：16

共 9 条

[1] △-匹配与边面全色数 [J].

王维凡，张克民 .

应用数学学报, 1999, (02) :236-242

[2] Total coloring of outer-1-planar graphs with near-independent crossings [J].

Zhang, Xin .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (03) :661-675

[3] The edge chromatic number of outer-1-planar graphs [J].

Zhang, Xin .

DISCRETE MATHEMATICS, 2016, 339 (04) :1393-1399

[4]

List total coloring of pseudo-outerplanar graphs [J] . Xin Zhang.&nbsp&nbspDiscrete Mathematics . 2013

[5] Edge covering pseudo-outerplanar graphs with forests [J].

Zhang, Xin ;

Liu, Guizhen ;

Wu, Jian-Liang .

DISCRETE MATHEMATICS, 2012, 312 (18) :2788-2799

[6] Coloring Plane Graphs with Independent Crossings [J].

Kral, Daniel ;

Stacho, Ladislav .

JOURNAL OF GRAPH THEORY, 2010, 64 (03) :184-205

[7]

Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs [J] . Wang Weifan,Ko-Wei Lih.&nbsp&nbspEuropean Journal of Combinatorics . 2001 (1)

[8] List edge and list total colourings of multigraphs [J].

Borodin, OV ;

Kostochka, AV ;

Woodall, DR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 71 (02) :184-204

[9] The polynomial method and restricted sums of congruence classes [J].

Alon, N ;

Nathanson, MB ;

Ruzsa, I .

JOURNAL OF NUMBER THEORY, 1996, 56 (02) :404-417

← 1 →