Precoloring extension of co-Meyniel graphs

DOI10.1007/S00373-007-0724-1MaRDI QIDQ995757zbMATHOpenAlexFDO

Authors Vincent Jost, Benjamin Lévêque, Frédéric Maffray

Publication date 10 September 2007

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0509004

zbMATH Keywords

perfect graphsArtemis graphMeyniel graphperfectnessPrecoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: The pre-coloring extension problem consists, given a graph $G$ and a subset of nodes to which some colors are already assigned, in finding a coloring of $G$ with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that ``PrExt perfect graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (``co-Artemis graphs, which are ``co-perfectly contractile graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.

Recommendations

• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension. I: Interval graphs
• scientific article; zbMATH DE number 1033812
• Precoloring extension on unit interval graphs
• scientific article; zbMATH DE number 772760

Cites work

• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• A class of perfectly contractile graphs
• Approximation results for the optimum cost chromatic partition problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Even pairs
• Geometric algorithms and combinatorial optimization
• Graph colorings with local constraints -- a survey
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension. I: Interval graphs
• Scheduling with incompatible jobs
• Slim graphs
• The strong perfect graph theorem
• You can't paint yourself into a corner

Cited in

(4)

• On the number of precolouring extensions
• Precoloring Extension for 2‐connected Graphs
• Precoloring extension for 2-connected graphs with maximum degree three
• Coloring Artemis graphs

This page was built for publication: Precoloring extension of co-Meyniel graphs

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