Improved square coloring of planar graphs

被引：5

作者：

Bousquet, Nicolas ^{[2
]}

Deschamps, Quentin ^{[2
]}

de Meyer, Lucas ^{[1
,2
]}

Pierron, Theo ^{[2
]}

机构：

[1] ENS Rennes, Dept Informat, Rennes, France

[2] Univ Lyon 1, Univ Lyon, LIRIS UMR CNRS 5205, F-69621 Lyon, France

来源：

DISCRETE MATHEMATICS | 2023年 / 346卷 / 04期

关键词：

Graph coloring; Square coloring; Planar graphs; Discharging method; Wegner conjecture;

D O I：

10.1016/j.disc.2022.113288

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that 32 Delta + 1colors are sufficient to square color every planar graph of maximum degree Delta. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that 2 Delta + 7colors are sufficient, which improves the best known bounds when 6 <= Delta <= 31. (c) 2022 Elsevier B.V. All rights reserved.

引用

页数：11

共 15 条

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

Agnarsson, G ;

Halldórsson, MM .

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

[2] A unified approach to distance-two colouring of graphs on surfaces [J].

Amini, Omid ;

Esperet, Louis ;

Van den Heuvel, Jan .

COMBINATORICA, 2013, 33 (03) :253-296

[3] EVERY PLANAR MAP IS 4 COLORABLE [J].

APPEL, K ;

HAKEN, W .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 82 (05) :711-712

[4]

Havet F., 2017, LIST COLOURING SQUAR

[5]

Hoffman A. J., 2003, SELECTED PAPERS ALAN, P377

[6]

Jonas T. K., 1993, Graph coloring analogues with a condition at distance two: L(2, 1)- labellings and list lambda-labellings

[7]

Krzyzinski M., 2021, COLORING SQUARES PLA

[8]

Madaras T., 2002, Discussiones Mathematicae Graph Theory, V22, P293, DOI 10.7151/dmgt.1176

[9] A bound on the chromatic number of the square of a planar graph [J].

Molloy, M ;

Salavatipour, MR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) :189-213

[10]

Thomassen C., 2001, APPL TUTTE CYCLE

← 1 2 →