Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods (Q2097169): Difference between revisions

This paper focuses on conflict-free colourings of graphs (those where the neighbourhood of every vertex contains some colour which appears on exactly one vertex: neighbourhood can be either closed, i.e. including the dominating vertex or open, i.e. not doing so) and unique maximum colourings (where, in some predefined ordering of the colours, the maximum colour appears only once in each neighbourhood). The focus is on planar graphs and it is often assumed that the colouring is also proper. A unique maximum colouring is clearly a conflict-free colouring. These ideas lead to consideration of the minimum number of colours required for such a colouring, analogous to the usual chromatic number, and the worst case of such a chromatic number over all graphs in a certain class. Amongst the new results presented is that the worst case improper unique maximum colouring number over all planar graphs with respect to open neighbourhoods is in the range 5 to 10 (all ranges quoted are inclusive of both endpoints) and for closed neighbourhoods the worst case improper unique maximum colouring number is in the range 4 to 6. For outerplanar graphs, as one might hope, one can reduce these ranges: for the open neighbourhoods it becomes 4 to 5, and for closed neighbourhoods 3 to 5. For conflict-free, the worst case is 6 to 10 and for closed neighbourhoods 6 to 8. For proper unique maximum over all outerplanar graphs, the answer for both open neighbourhoods and closed neighbourhoods is determined exactly -- it is 5.