The edge chromatic number of outer-1-planar graphs

作者: Xin Zhang

DOI: 10.1016/J.DISC.2015.12.009

关键词:

摘要: A graph is outer-1-planar if each block has an embedding in the plane such a way that vertices lie on fixed circle and edges inside disk of this with them crossing at most one another. In paper, we completely determine edge chromatic number outer 1-planar graphs.

参考文章(12)
Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber, Recognizing Outer 1-Planar Graphs in Linear Time graph drawing. pp. 107- 118 ,(2013) , 10.1007/978-3-319-03841-4_10
Guizhen Liu, Xin Zhang, Total coloring of pseudo-outerplanar graphs arXiv: Combinatorics. ,(2011)
HOOMAN REISI DEHKORDI, PETER EADES, EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING International Journal of Computational Geometry and Applications. ,vol. 22, pp. 543- 557 ,(2012) , 10.1142/S021819591250015X
Daniel P. Sanders, Yue Zhao, Planar Graphs of Maximum Degree Seven are Class I Journal of Combinatorial Theory, Series B. ,vol. 83, pp. 201- 212 ,(2001) , 10.1006/JCTB.2001.2047
Daniel P. Sanders, Yue Zhao, Coloring the Faces of Convex Polyhedra so That Like Colors Are Far Apart Journal of Combinatorial Theory, Series B. ,vol. 85, pp. 348- 360 ,(2002) , 10.1006/JCTB.2001.2109
Xin Zhang, List total coloring of pseudo-outerplanar graphs☆ Discrete Mathematics. ,vol. 313, pp. 2297- 2306 ,(2013) , 10.1016/J.DISC.2013.06.007
Xin Zhang, Jian-Liang Wu, On edge colorings of 1-planar graphs Information Processing Letters. ,vol. 111, pp. 124- 128 ,(2011) , 10.1016/J.IPL.2010.11.001
Ian Holyer, The NP-Completeness of Edge-Coloring SIAM Journal on Computing. ,vol. 10, pp. 718- 720 ,(1981) , 10.1137/0210055
Carsten Thomassen, Rectilinear drawings of graphs Journal of Graph Theory. ,vol. 12, pp. 335- 341 ,(1988) , 10.1002/JGT.3190120306
Xin Zhang, Jingjing Tian, Pseudo-outerplanar graphs and chromatic conjectures. Ars Combinatoria. ,vol. 114, pp. 353- 361 ,(2014)