2-DISTANCE 4-COLORABILITY OF PLANAR SUBCUBIC GRAPHS WITH GIRTH AT LEAST 22

被引：7

作者：

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

Ivanova, Anna O. ^{[3
,4
]}

机构：

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

[2] Novosibirsk State Univ, Novosibirsk 630090, Russia

[3] Yakutsk State Univ, Inst Math, Yakutsk 677891, Russia

[4] North Eastern Fed Univ, Yakutsk 677891, Russia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2012年 / 32卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

planar graph; subcubic graph; 2-distance coloring; COLORING SQUARES;

D O I：

10.7151/dmgt.1592

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The trivial lower bound for the 2-distance chromatic number chi(2)(G) of any graph G with maximum degree Delta is Delta +1. It is known that chi(2) = Delta + 1 if the girth g of G is at least 7 and Delta is large enough. There are graphs with arbitrarily large Delta and g <= 6 having chi(2) (C) >= Delta + 2. We prove the 2-distance 4-colorability of planar subcubic graphs with g >= 22.

引用

页码：141 / 151

页数：11

共 21 条

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

Agnarsson, G ;

Halldórsson, MM .

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

[2]

Agnarsson G, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P654

[3]

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

[4] 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

[5]

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

[6]

Borodin O.V., 2005, DISKRETN ANAL ISSLED, V12, P32

[7] 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

[8]

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

[9]

[Бородин Олег Вениаминович Borodin Oleg Veniaminovich], 2011, [Дискретный анализ и исследование операций, Diskretnyi analiz i issledovanie operatsii], V18, P18

[10]

BORODIN OV, 2001, DISKRETN ANAL ISSL 1, V8, P9

← 1 2 3 →