Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911821759250432 |
|---|---|
| author | Beaudou, Laurent Brosse, Caroline Defrain, Oscar Foucaud, Florent Lagoutte, Aurélie Limouzy, Vincent Pastor, Lucas |
| author_facet | Beaudou, Laurent Brosse, Caroline Defrain, Oscar Foucaud, Florent Lagoutte, Aurélie Limouzy, Vincent Pastor, Lucas |
| contents | The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_n$, the "First-Fit" greedy colouring algorithm colours the vertices in the order of $σ$ by assigning to each vertex the smallest colour unused in its neighbourhood.
By restricting this procedure to vertex orderings that are connected, we obtain {\em connected greedy colourings}. For some graphs, all connected greedy colourings use exactly $χ(G)$ colours; they are called {\em good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only $χ(G)$ colours; they are called {\em ugly graphs}.
We show that no perfect graph is ugly. We also give simple proofs of this fact for subclasses of perfect graphs (block graphs, comparability graphs), and show that no $K_4$-minor free graph is ugly.
Moreover, our proofs are constructive, and imply the existence of polynomial-time algorithms to compute good connected orderings for these graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_14003 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly Beaudou, Laurent Brosse, Caroline Defrain, Oscar Foucaud, Florent Lagoutte, Aurélie Limouzy, Vincent Pastor, Lucas Discrete Mathematics Combinatorics The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_n$, the "First-Fit" greedy colouring algorithm colours the vertices in the order of $σ$ by assigning to each vertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, we obtain {\em connected greedy colourings}. For some graphs, all connected greedy colourings use exactly $χ(G)$ colours; they are called {\em good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only $χ(G)$ colours; they are called {\em ugly graphs}. We show that no perfect graph is ugly. We also give simple proofs of this fact for subclasses of perfect graphs (block graphs, comparability graphs), and show that no $K_4$-minor free graph is ugly. Moreover, our proofs are constructive, and imply the existence of polynomial-time algorithms to compute good connected orderings for these graph classes. |
| title | Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2110.14003 |