Incidence Coloring of Outer-1-planar Graphs
查看参考文献18篇
|
文摘
|
A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge. It is known that every outer-1-planar graph is a planar partial 3-tree. In this paper, we conjecture that every planar graph G has a proper incidence (Δ(G) + 2)-coloring and confirm it for outer-1-planar graphs with maximum degree at least 8 or with girth at least 4. Specifically, we prove that every outer-1-planar graph G has an incidence (Δ(G)+3, 2)-coloring, and every outer-1-planar graph G with maximum degree at least 8 or with girth at least 4 has an incidence (Δ(G) + 2, 2)-coloring. |
|
来源
|
Acta Mathematicae Applicatae Sinica-English Series
,2024,40(3):840-848 【核心库】
|
|
DOI
|
10.1007/s10255-024-1126-3
|
|
关键词
|
incidence coloring
;
outer-1-planar graph
;
planar graph
|
|
地址
|
School of Mathematics and Statistics,Xidian University, Xi'an, 710071
|
|
语种
|
英文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
0168-9673 |
|
学科
|
数学 |
|
基金
|
Supported in part by the Natural Science Basic Research Program of Shaanxi
;
the Fundamental Research Funds for the Central Universities
;
国家自然科学基金
|
|
文献收藏号
|
CSCD:7727602
|
参考文献 共
18
共1页
|
|
1.
Algor I. The star arboricity of graphs.
Discrete Math,1989,75:11-22
|
CSCD被引
9
次
|
|
|
|
|
2.
Auer C. Recognizing outer 1-planar graphs in linear time.
Graph Grawing, GD 2013, Lecture Notes in Comput. Sci,8242,2013:107-118
|
CSCD被引
1
次
|
|
|
|
|
3.
Auer C. Outer-1-planar graphs.
Algorithmica,2016,74:1293-1320
|
CSCD被引
4
次
|
|
|
|
|
4.
Bonamy M. 2-distance coloring of sparse graphs.
J. Graph Theory,2014,77(3):190-218
|
CSCD被引
2
次
|
|
|
|
|
5.
Bondy J A.
Graph Theory,2008
|
CSCD被引
195
次
|
|
|
|
|
6.
Brualdi R A. Incidence and strong edge colorings of graphs.
Discrete Math,1993,122:51-58
|
CSCD被引
16
次
|
|
|
|
|
7.
Guiduli B. On incidence coloring and star arboricity of graphs.
Discrete Math,1997,163:275-278
|
CSCD被引
7
次
|
|
|
|
|
8.
Hosseini Dolama M. On the maximum average degree and the incidence chromatic number of a graph.
Discrete Math. Theoret. Comput. Sci,2005,7:203-216
|
CSCD被引
1
次
|
|
|
|
|
9.
Hosseini Dolama M. Incidence coloring of k-degenerated graphs.
Discrete Math,2004,283(1/3):121-128
|
CSCD被引
1
次
|
|
|
|
|
10.
Kardos F. Incidence coloring-Cold cases.
Discuss. Math. Graph Theory,2020,40:345-354
|
CSCD被引
1
次
|
|
|
|
|
11.
Li Y. The structure and the list 3-dynamic coloring of outer-1-planar graphs.
Discrete Math. Theoret. Comput. Sci,2021,23(3):#4
|
CSCD被引
1
次
|
|
|
|
|
12.
Maydanskiy M. The incidence coloring conjecture for graphs of maximum degree three.
Discrete Math,2005,292:131-141
|
CSCD被引
5
次
|
|
|
|
|
13.
Shiu W C. Invalid proofs on incidence coloring.
Discrete Math,2008,308(24):6575-6580
|
CSCD被引
2
次
|
|
|
|
|
14.
Sopena E.
www.labri.fr/perso/sopena/TheIncidenceColoringPage
|
CSCD被引
1
次
|
|
|
|
|
15.
Wang W F. Labeling planar graphs with conditions on girth and distance two.
SIAM J. Discrete Math,2003,17(2):264-275
|
CSCD被引
14
次
|
|
|
|
|
16.
Yang D. Fractional incidence coloring and star arboricity of graphs.
Ars Combin,2012,105:213-224
|
CSCD被引
1
次
|
|
|
|
|
17.
Zhang X. List total coloring of pseudo-outerplanar graphs.
Discrete Math,2013,313:2297-2306
|
CSCD被引
6
次
|
|
|
|
|
18.
Zhang X. Edge covering pseudo-outerplanar graphs with forests.
Discrete Math,2012,312:2788-2799
|
CSCD被引
7
次
|
|
|
|
|
了解气象卫星更多信息，请访问