Fixed parameter algorithms for restricted coloring problems

Details Fixed parameter algorithms for restricted coloring problems Fixed parameter algorithms for restricted coloring problems

2011-06-30

arxiv.org/abs/1107.0056v2

Computer Science

Discrete Mathematics

Scientific paper

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$-tidy graphs and $(q,q-4)$-graphs, for every fixed $q$. These classes include cographs, $P_4$-sparse and $P_4$-lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$, which is the minimum $q$ such that $G$ is a $(q,q-4)$-graph. We also prove that every connected $(q,q-4)$-graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.

Affiliated with

Also associated with

No associations

Rating

Fixed parameter algorithms for restricted coloring problems 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 Fixed parameter algorithms for restricted coloring problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed parameter algorithms for restricted coloring problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480050