Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Krivelevich, M., Sudakov, B.: Subgraphs with a large cochromatic number. J. Graph Theory 25, 295–297 (1997)
Babel, L., Kloks, T., Kratochvl, J., Kratsch, D., Muller, H., Olariu, S.: Efficient algorithms for graphs with few P4s. Discrete Mathematics 235(23), 29–51 (2001)
Babel, L., Olariu, S.: On the structure of graphs with few P 4’s. Discrete Applied Mathematics 84, 1–13 (1998)
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Bondy, A., Murty, U.S.R.: Graph Theory. Springer (2008)
Brandstädt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics 152, 47–54 (1996)
Bravo, R.S.F., Klein, S., Nogueira, L.T.: Characterizing (k,ℓ)-partitionable cographs. In: 7th International Colloquium on Graph Theory, Hyeres. Electronic Notes in Discrete Mathematics vol. 22, pp. 277–280 (2005)
Bravo, R., Klein, S., Nogueira, L., Protti, F.: Characterization and recognition of P4-sparse graphs partitionable into k independent sets and ℓ cliques. Discrete Applied Mathematics 159, 165–173 (2011)
Bravo, R., Klein, S., Nogueira, L., Protti, F., Sampaio, R.: Partitioning extended P 4-laden graphs into cliques and stable sets (submitted, 2011)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear Time Solvable Optimization Problems on Certain Graph Families. In: Hromkovič, J., Sýkora, O. (eds.) WG 1998. LNCS, vol. 1517, pp. 1–16. Springer, Heidelberg (1999)
Demange, M., Ekim, T., de Werra, D.: Partitioning cographs into cliques and stable sets. Discrete Optimization 2, 145–153 (2005)
Erdős, P., Gimbel, J.: Some problems and results in cochromatic theory. In: Quo Vadis, Graph Theory?, pp. 261–264. North-Holland, Amsterdam (1993)
Erdős, P., Gimbel, J., Kratsch, D.: Some extremal results in cochromatic and dichromatic theory. J. Graph Theory 15, 579–585 (1991)
Erdős, P., Gimbel, J., Straight, H.J.: Chromatic number versus cochromatic number in graphs with bounded clique number. European J. Combin. 11, 235–240 (1990)
Feder, T., Hell, P.: Matrix partitions of perfect graphs. Discrete Mathematics 306, 2450–2460 (2006)
Feder, T., Hell, P., Hochstttler, W.: Generalized colourings (matrix partitions) of cographs. In: Graph Theory in Paris. Trends in Mathematics, pp. 149–167 (2007)
Feder, T., Hell, P., Klein, S., Motwani, R.: Complexity of list partition. In: 31st Annual ACM Symposium on Theory of Computing, pp. 464–472. Plenum Press, New York (1999)
Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM Journal on Discrete Mathematics 16, 449–478 (2003)
Fomin, F.V., Kratsch, D., Novelli, J.C.: Approximating minimum cocolorings. Information Processing Letters 84, 285–290 (2002)
Heggernes, P., Kratsch, D., Lokshtanov, D., Raman, V., Saurabh, S.: Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 334–345. Springer, Heidelberg (2010)
Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics 141, 185–194 (2004)
Jamison, B., Olariu, S.: A tree representation for P4-sparse graphs. Discrete Applied Mathematics 35(2), 115–129 (1992)
Lesniak, L., Straight, H.J.: The cochromatic number of a graph. Ars Combinatoria 3, 39–46 (1977)
Wagner, K.: Monotonic coverings of finite sets. Elektron. Inform. Kybernet. 20, 633–639 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Campos, V., Klein, S., Sampaio, R., Silva, A. (2011). Two Fixed-Parameter Algorithms for the Cocoloring Problem. In: Asano, T., Nakano, Si., Okamoto, Y., Watanabe, O. (eds) Algorithms and Computation. ISAAC 2011. Lecture Notes in Computer Science, vol 7074. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25591-5_65
Download citation
DOI: https://doi.org/10.1007/978-3-642-25591-5_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25590-8
Online ISBN: 978-3-642-25591-5
eBook Packages: Computer ScienceComputer Science (R0)