Geodesic
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

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 $\sigma= v_1,\dots,v_n$, the "First-Fit" greedy colouring algorithm colours the vertices in the order of $\sigma$ 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 $\chi(G)$ colours; they are called {\em good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only $\chi(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.
DOI : 10.46298/dmtcs.8715
Classification : 05C10, 05C15, 05C17, 05C83, 05C85 
@article{DMTCS_2024_25_2_a21,
     author = {Beaudou, Laurent and Brosse, Caroline and Defrain, Oscar and Foucaud, Florent and Lagoutte, Aur\'elie and Limouzy, Vincent and Pastor, Lucas},
     title = {Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2023-2024},
     doi = {10.46298/dmtcs.8715},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.8715/}
}
TY  - JOUR
AU  - Beaudou, Laurent
AU  - Brosse, Caroline
AU  - Defrain, Oscar
AU  - Foucaud, Florent
AU  - Lagoutte, Aurélie
AU  - Limouzy, Vincent
AU  - Pastor, Lucas
TI  - Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.8715/
DO  - 10.46298/dmtcs.8715
LA  - en
ID  - DMTCS_2024_25_2_a21
ER  - 
%0 Journal Article
%A Beaudou, Laurent
%A Brosse, Caroline
%A Defrain, Oscar
%A Foucaud, Florent
%A Lagoutte, Aurélie
%A Limouzy, Vincent
%A Pastor, Lucas
%T Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.8715/
%R 10.46298/dmtcs.8715
%G en
%F DMTCS_2024_25_2_a21
Beaudou, Laurent; Brosse, Caroline; Defrain, Oscar; Foucaud, Florent; Lagoutte, Aurélie; Limouzy, Vincent; Pastor, Lucas. Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi : 10.46298/dmtcs.8715. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.8715/

Cité par Sources :