betaFeedback

WorksMathematics

Unique-maximum colourings of planar graphs with respect to neighbourhoods

Abstract

A colouring of the vertices of a graph by positive integers is a unique-maximum colouring with respect to open (resp. closed) neighbourhoods if the maximum colour appears exactly once in the open (resp. closed) neighbourhood of every vertex. Fabrici, Lužar, Rindošová and Soták (Discrete Appl. Math. 324 (2023) 80-92) conjectured that four colours suffice for closed neighbourhoods in planar graphs. We prove this conjecture by colouring a suitable independent dominating set with the three largest colours. They further conjectured that six colours suffice if the colouring is also proper. We disprove this conjecture by a planar graph which needs seven colours, and we show that seven colours always suffice. For open neighbourhoods, we show that eight colours suffice, even for proper colourings, which improves the previous bound of ten. In the proper case, our graph again needs seven colours. If the colouring need not be proper and the graph has no vertices of degree 2, then six colours suffice.

Paper details

vlnc:W_2xxf9shx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…