\(2\)-distance coloring of planar graphs with maximum degree \(5\)
type: Item
instance of: scholarly article
title: \(2\)-distance coloring of planar graphs with maximum degree \(5\)
zbMATH Open document ID: 1483.05059
author: Ming Chen
author: Shan Zhou
author: Lianying Miao
published in: Discrete Mathematics
publication date: 2022-02-14T00:00:00Z
review text: A 2-distance colouring of a graph is an assignment of colours to the vertices such that vertices at distance 1 or 2 from each other have different colours. The 2-distance colouring number \(\chi_{2}(G)\) is the smallest \(k\) such that there is a 2-distance colouring with \(k\) colours. So for example every \(n\)-vertex graph \(G\) of diameter 2 has \(\chi_{2}(G)=n\). Note that \(\chi_{2}(G)\geq \chi(G)\) where \(\chi\) is the usual chromatic number. The paper under review considers proper 2-distance colourings of planar graphs of maximum degree 5. The main result being that such graphs have 2-distance colouring number at most 19. This is related to an influential, and still unsolved for some small values of \(\Delta\) the maximum degree, conjecture of \textit{G. Wegner} [Graphs with given diameter and a coloring problem. Techn. Rep., University of Dortmund (1977)] bounding above the 2-distance colouring number of a planar graph of maximum degree \(\Delta\) in terms of \(\Delta\). The previous best upper bound was 20. The proof uses configurations. A putative counterexample \(G\) with \(\vert V(G)\vert +\vert E(G)\vert\) as small as possible is taken. A number of reducible configurations are given and discharging is used, along with Euler's formula, to derive a contradiction. The authors speculate that it may be possible to reduce the upper bound 19 to 10.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7473529
zbMATH Keywords: planar graph
zbMATH Keywords: \(2\)-distance \(k\)-coloring
zbMATH Keywords: discharging
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: j.disc.2021.112766
OpenAlex ID: W4205307969
cites work: Coloring Powers of Planar Graphs
cites work: Labelling Graphs with a Condition at Distance 2
cites work: Coloring the square of a planar graph
cites work: A bound on the chromatic number of the square of a planar graph
cites work: Minimum 2-distance coloring of planar graphs and channel assignment
DOI: 10.1016/J.DISC.2021.112766
description: scientific article; zbMATH DE number 7473529