Using stable sets to bound the chromatic number

DOI10.1016/S0020-0190(03)00266-7MaRDI QIDQ1014408zbMATH OpenFDO

Authors Dominique De Werra, Pierre Hansen

Publication date 28 April 2009

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

zbMATH Keywords

algorithmschromatic numbergraph coloringstable setlongest path

Mathematics Subject Classification ID

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

Recommendations

• A generalization of the Gallai-Roy theorem
• A dualistic approach to bounding the chromatic number of a graph
• Bounded Stable Sets: Polytopes and Colorings
• On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem
• About colorings, stability and paths in directed graphs

Cites work

• scientific article; zbMATH DE number 3150488 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2156665 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A generalization of the Gallai-Roy theorem
• Diperfect graphs
• Generalized colorings and avoidable orientations
• Mixed graph colorings
• Nombre chromatique et plus longs chemins d'un graphe
• On conjectures of Graffiti

Cited in

(7)

• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• A supernodal formulation of vertex colouring with applications in course timetabling
• A generalization of Gale's lemma
• \([r,s,t]\)-coloring of trees and bipartite graphs
• On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem
• Variations on the Roy-Gallai theorem

Describes a project that uses

Uses Software

• GRAFFITI

This page was built for publication: Using stable sets to bound the chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014408)