PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS

被引：23

作者：

Borodin, Oleg V. ^{[1
,2
]}

Ivanova, Anna O. ^{[3
]}

机构：

[1] Russian Acad Sci, Inst Math, Siberian Branch, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Novosibirsk 630090, Russia

[3] Ammosov North Eastern Fed Univ, Inst Math, Yakutsk 677891, Russia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2013年 / 33卷 / 04期

基金：

俄罗斯基础研究基金会;

关键词：

planar graph; edge coloring; 2-distance coloring; strong edge-coloring; COLORING SQUARES; GIRTH; INDEX;

D O I：

10.7151/dmgt.1708

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every planar graph with maximum degree A is strong edge (2 Delta - 1)-colorable if its girth is at least 40[Delta/2] vertical bar 1. The bound 2 Delta - 1 is reached at any graph that has two adjacent vertices of degree Delta.

引用

页码：759 / 770

页数：12

共 34 条

[1] Coloring powers of planar graphs [J].

Agnarsson, G ;

Halldórsson, MM .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (04) :651-662

[2] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10 [J].

ANDERSEN, LD .

DISCRETE MATHEMATICS, 1992, 108 (1-3) :231-252

[3]

Borodin OV, 2006, SIB ELECTRON MATH RE, V3, P441

[4] List 2-facial 5-colorability of plane graphs with girth at least 12 [J].

Borodin, O. V. ;

Ivanova, A. O. .

DISCRETE MATHEMATICS, 2012, 312 (02) :306-314

[5] 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18 [J].

Borodin, O. V. ;

Ivanova, A. O. .

DISCRETE MATHEMATICS, 2009, 309 (23-24) :6496-6502

[6]

Borodin O.V., 2005, DISKRETN ANAL ISSL 1, V1 12

[7]

Borodin O.V., 2004, Siberian Electronic Math. Reports, V1, P129

[8] 2-DISTANCE 4-COLORABILITY OF PLANAR SUBCUBIC GRAPHS WITH GIRTH AT LEAST 22 [J].

Borodin, Oleg V. ;

Ivanova, Anna O. .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (01) :141-151

[9] List 2-distance (Δ+2)-coloring of planar graphs with girth six [J].

Borodin, Oleg V. ;

Ivanova, Anna O. .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1257-1262

[10]

Borodin Oleg V., 2004, SIB ELEKT MAT IZV, V1, P76

← 1 2 3 4 →