Advertisement
Published in:
2011 | OriginalPaper | Chapter
Two Fixed-Parameter Algorithms for the Cocoloring Problem
Authors : Victor Campos, Sulamita Klein, Rudini Sampaio, Ana Silva
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A (
k
,ℓ)-cocoloring of a graph
G
is a partition of the vertex set of
G
into at most
k
independent sets and at most ℓ cliques. Given a graph
G
and integers
k
and ℓ, the
Cocoloring Problem
is the problem of deciding if
G
has a (
k
,ℓ)-cocoloring. It is known that determining the cochromatic number (the minimum
k
+ ℓ such that
G
is (
k
,ℓ)-cocolorable) is NP-hard [24]. In 2011, Bravo et al. obtained a polynomial time algorithm for
P
4
-sparse graphs [8]. In this paper, we generalize this result by obtaining a polynomial time algorithm for (
q
,
q
− 4)-graphs for every fixed
q
, which are the graphs such that every subset of at most
q
vertices induces at most
q
− 4 induced
P
4
’s.
P
4
-sparse graphs are (5,1)-graphs. Moreover, we prove that the cocoloring problem is FPT when parameterized by the treewidth
tw
(
G
) or by the parameter
q
(
G
), defined as the minimum integer
q
≥ 4 such that
G
is a (
q
,
q
− 4)-graph.