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

DOI10.46298/dmtcs.8715zbMATH Open1548.05108MaRDI QIDQ6599810

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

Publication date: 6 September 2024

Published in: Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

zbMATH Keywords

perfect graphsblock graphscomparability graphsconnected greedy colouring\(K_4\)-minor-free graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Connected greedy coloring of \(H\)-free graphs
• Connected sequential colourings
• Some perfect coloring properties of graphs
• Some simplified NP-complete graph problems
• A partial k-arboretum of graphs with bounded treewidth
• Hard-to-color graphs for connected sequential colorings
• Complexity of Grundy coloring and its variants
• On the semi-perfect elimination
• A note on connected greedy edge colouring
• Topology of series-parallel networks
• Some classes of perfectly orderable graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Reducibility among Combinatorial Problems
• Connected Greedy Colourings
• An \(O(n^2)\) algorithm to color Meyniel graphs

This page was built for publication: Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly