Deciding k-colourability of $P_5$-free graphs in polynomial time

Details Deciding k-colourability of $P_5$-free graphs in polynomial time Deciding k-colourability of $P_5$-free graphs in polynomial time

2007-02-07

arxiv.org/abs/cs/0702043v1

Computer Science

Data Structures and Algorithms

Scientific paper

The problem of computing the chromatic number of a $P_5$-free graph is known
to be NP-hard. In contrast to this negative result, we show that determining
whether or not a $P_5$-free graph admits a $k$-colouring, for each fixed number
of colours $k$, can be done in polynomial time. If such a colouring exists, our
algorithm produces it.

Affiliated with

Also associated with

No associations

Rating

Deciding k-colourability of $P_5$-free graphs in polynomial time 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 Deciding k-colourability of $P_5$-free graphs in polynomial time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deciding k-colourability of $P_5$-free graphs in polynomial time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218456