On coloring problems with local constraints

DOI10.1016/j.disc.2012.03.019zbMath1243.05077MaRDI QIDQ5891606

Gianpaolo Oriolo, Yuri Faenza, Flavia Bonomo-Braberman

Publication date: 18 June 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.03.019

zbMATH Keywords

computational complexity; graph coloring; unit interval graphs; clique-trees

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Polyhedral studies of vertex coloring problems: the standard formulation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure and linear time recognition of 3-leaf powers
• Completely separable graphs
• An optimal greedy heuristic to color interval graphs
• A unified approach to domination problems on interval graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Precoloring extension. I: Interval graphs
• Generalized coloring for tree-like graphs
• Precoloring extension on unit interval graphs
• On Graph Powers for Leaf-Labeled Trees
• Solving a Real-World Train Unit Assignment Problem
• Approximation results for the optimum cost chromatic partition problem
• Precoloring Extension III: Classes of Perfect Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Exploring the complexity boundary between coloring and list-coloring