Using stable sets to bound the chromatic number

DOI10.1016/S0020-0190(03)00266-7zbMath1161.68704MaRDI QIDQ1014408

Dominique de Werra, Pierre Hansen

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmsstable setgraph coloringchromatic numberlongest path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

A supernodal formulation of vertex colouring with applications in course timetabling, \([r,s,t\)-coloring of trees and bipartite graphs], A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

Uses Software

• GRAFFITI

Cites Work

• On conjectures of Graffiti
• Mixed graph colorings
• Diperfect graphs
• Generalized colorings and avoidable orientations
• Nombre chromatique et plus longs chemins d'un graphe
• A generalization of the Gallai-Roy theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item