Precoloring co-Meyniel graphs

Details Precoloring co-Meyniel graphs Precoloring co-Meyniel graphs

2005-09-02

arxiv.org/abs/cs/0509004v1

Graphs and Combinatorics 23, 3 (07/07/2007) 291-301

Computer Science

Discrete Mathematics

Scientific paper

10.1007/s00373-007-0724-1

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.

Affiliated with

Also associated with

No associations

Rating

Precoloring co-Meyniel graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Precoloring co-Meyniel graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Precoloring co-Meyniel graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-193157