On coloring problems with local constraints

DOI10.1016/j.disc.2012.03.019zbMath1243.05077OpenAlexW2176348781MaRDI 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 complexitygraph coloringunit interval graphsclique-trees

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

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

This page was built for publication: On coloring problems with local constraints