Laurent Beaudou ; Caroline Brosse ; Oscar Defrain ; Florent Foucaud ; Aurélie Lagoutte et al. - Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

dmtcs:8715 - Discrete Mathematics & Theoretical Computer Science, April 2, 2024, vol. 25:2 - https://doi.org/10.46298/dmtcs.8715
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the uglyArticle

Authors: Laurent Beaudou ; Caroline Brosse ; Oscar Defrain ; Florent Foucaud ; Aurélie Lagoutte ; Vincent Limouzy ; Lucas Pastor

    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.


    Volume: vol. 25:2
    Section: Graph Theory
    Published on: April 2, 2024
    Accepted on: November 19, 2023
    Submitted on: November 17, 2021
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 242 times.
    This article's PDF has been downloaded 137 times.