Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods (Q2097169): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4300861154 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 2202.02570 / rank | |||
Normal rank |
Revision as of 02:03, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods |
scientific article |
Statements
Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods (English)
0 references
11 November 2022
0 references
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.
0 references
plane graph
0 references
proper conflict-free coloring
0 references
proper unique-maximum coloring
0 references
closed neighborhood
0 references
open neighborhood
0 references