Light subgraphs in the family of 1-planar graphs with high minimum degree

被引：7

作者：

Zhang, Xin ^{[1
]}

Liu, Gui Zhen ^{[1
]}

Wu, Jian Liang ^{[1
]}

机构：

[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2012年 / 28卷 / 06期

基金：

中国国家自然科学基金;

关键词：

1-Planar graph; lightness; height; discharging; EDGE COLORINGS;

D O I：

10.1007/s10114-011-0439-3

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of (2)a( (1)a(a) (2)) with all vertices of degree at most 12. In addition, we also prove the existence of a graph (1)a( (1)a(a) (2)) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.

引用

页码：1155 / 1168

页数：14

共 23 条

[1] Coloring vertices and faces of locally planar graphs [J].

Albertson, Michael O. ;

Mohar, Bojan .

GRAPHS AND COMBINATORICS, 2006, 22 (03) :289-295

[2]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[3]

Borodin O. V., 2009, J APPL IND MATH, V3, P28

[4] Acyclic colouring of 1-planar graphs [J].

Borodin, OV ;

Kostochka, AV ;

Raspaud, A ;

Sopena, E .

DISCRETE APPLIED MATHEMATICS, 2001, 114 (1-3) :29-41

[5] A NEW PROOF OF THE 6 COLOR THEOREM [J].

BORODIN, OV .

JOURNAL OF GRAPH THEORY, 1995, 19 (04) :507-521

[6]

BORODIN OV, 1984, METODY DISKRET ANAL, V41, P12

[7] The structure of 1-planar graphs [J].

Fabrici, Igor ;

Madaras, Tomas .

DISCRETE MATHEMATICS, 2007, 307 (7-8) :854-865

[8]

Hudak David, 2009, Discussiones Mathematicae Graph Theory, V29, P385, DOI 10.7151/dmgt.1454

[9] On local properties of 1-planar graphs with high minimum degree [J].

Hudak, David ;

Madaras, Tomas .

ARS MATHEMATICA CONTEMPORANEA, 2011, 4 (02) :245-254

[10] Minimal non-1-planar graphs [J].

Korzhik, Vladimir P. .

DISCRETE MATHEMATICS, 2008, 308 (07) :1319-1327

← 1 2 3 →