Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

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...

Full description

Bibliographic Details
Main Authors: Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2024-04-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
Online Access:https://dmtcs.episciences.org/8715/pdf