On coloring problems with local constraints

DOI10.1016/J.DISC.2012.03.019MaRDI QIDQ5891606zbMATH OpenOpenAlexFDO

Authors Yuri Faenza, Gianpaolo Oriolo, Flavia Bonomo

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

clique-treescomputational complexitygraph coloringunit interval graphs

Mathematics Subject Classification ID

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

Recommendations

• On coloring problems with local constraints
• Between coloring and list-coloring: -coloring.
• scientific article; zbMATH DE number 1033812
• Precoloring extension on unit interval graphs
• Exploring the complexity boundary between coloring and list-coloring

Cites work

• A unified approach to domination problems on interval graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An optimal greedy heuristic to color interval graphs
• Approximation results for the optimum cost chromatic partition problem
• Completely separable graphs
• Exploring the complexity boundary between coloring and list-coloring
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 5158493 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• On graph powers for leaf-labeled trees
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension on unit interval graphs
• Precoloring extension. I: Interval graphs
• Solving a real-world train unit assignment problem
• Structure and linear time recognition of 3-leaf powers
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(6)

• Polyhedral studies of vertex coloring problems: the standard formulation
• Locality-preserving allocations problems and coloured bin packing
• Between coloring and list-coloring: -coloring.
• On coloring problems with local constraints
• Exploring the complexity boundary between coloring and list-coloring
• Thinness and its variations on some graph families and coloring graphs of bounded thinness

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

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