Light Edges in 3-Connected 2-Planar Graphs With Prescribed Minimum Degree

被引：1

作者：

Lu, Zai Ping ^{[1
]}

Song, Ning ^{[1
]}

机构：

[1] Nankai Univ, LPMC TJKLC, Ctr Combinator, Tianjin 300071, Peoples R China

来源：

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY | 2018年 / 41卷 / 03期

关键词：

2-planar graph; Light edge; Weight; 1-PLANAR GRAPHS; COLORINGS; CROSSINGS;

D O I：

10.1007/s40840-016-0389-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is called 2-planar if it can be drawn in the plane such that each edge is crossed by at most other two edges. The weight of an edge is the sum of degrees of its ends. In the present paper, we focus on 3-connected 2-planar graphs with minimum degree 6 and show the existence of edges with weight at most 30 by a discharging process.

引用

页码：1265 / 1274

页数：10

共 16 条

[1]

Bondy J.A., 2008, GTM

[2]

BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180

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

Borodin, OV ;

Kostochka, AV ;

Raspaud, A ;

Sopena, E .

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

[4]

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

[5]

Czap J, 2013, ELECTRON J COMB, V20

[6] 1-planarity of complete multipartite graphs [J].

Czap, Julius ;

Hudak, David .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) :505-512

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

Fabrici, Igor ;

Madaras, Tomas .

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

[8]

Grunbaum B., 1976, INT TEORIE COMBINATO, V1, P451

[9] LIGHT EDGES IN 1-PLANAR GRAPHS WITH PRESCRIBED MINIMUM DEGREE [J].

Hudak, David ;

Sugerek, Peter .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (03) :545-556

[10] Light subgraphs of graphs embedded in the plane-A survey [J].

Jendrol', S. ;

Voss, H. -J. .

DISCRETE MATHEMATICS, 2013, 313 (04) :406-421

← 1 2 →