Abstract
A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A, B, C, D such that there are all possible edges between A and B, and no edges between C and D. We present a polynomial-time algorithm for testing whether a graph admits a skew partition. Our algorithm solves the more general list skew partition problem, where the input contains, for each vertex, a list containing some of the labels A, B, C, D of the four parts. Our polynomial-time algorithm settles the complexity of the original partition problem proposed by Chvátal, and answers a recent question of Feder, Hell, Klein and Motwani.
Research partially supported by CNPq, MCT/FINEP PRONEX Project 107/97, CAPES(Brazil)/COFECUB(France) Project 213/97, FAPERJ, and by FAPESP Proc. 96/04505-2.
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., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125–134 (1992)
Berge, C.: Les problèmes de coloration en théorie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123–160 (1960)
Chvátal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51–53 (1984)
Chvátal, V.: Star-Cutsets and perfect graphs. J. Combin. Theory Ser. B 39, 189–199 (1985)
Cornuéjols, G., Reed, B.: Complete multi-partite cutsets in minimal imperfect graphs. J. Combin. Theory Ser. B 59, 191–198 (1993)
Everett, H., Klein, S., Reed, B.: An optimal algorithm for finding clique-cross partitions. Congr. Numer. 135, 171–177 (1998)
Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Combin. Theory Ser. B 72, 236–250 (1998)
Feder, T., Hell, P., Huang, J.: List homomorphisms to bipartite graphs (manuscript)
Feder, T., Hell, P., Huang, J.: List homomorphisms to general graphs (manuscript)
Feder, T., Hell, P., Klein, S., Motwani, R.: Complexity of graph partition problems. In: Proceedings of the thirty-first ACM Symposium on Theory of Computing, STOC 1999, pp. 464–472 (1999)
de Figueiredo, C.M.H., Klein, S., Kohayakawa, Y., Reed, B.: Finding Skew Partitions Efficiently. Technical Report ES-503/99, COPPE/UFRJ, Brazil, Available at ftp://ftp.cos.ufrj.br/pub/tech_reps/es50399.ps.gz
Fleischner, H., Stiebitz, M.: A solution of a coloring problem of P. Erdös. Discrete Math. 101, 39–48 (1992)
Hell, P., Nešetřil, J.: On the complexity of H-coloring. J. Combin. Theory Ser. B 48, 92–110 (1990)
Hoàng, C.T.: Perfect Graphs. Ph.D. Thesis, School of Computer Science, McGill University, Montreal (1985)
MacGillivray, G., Yu, M.L.: Generalized partitions of graphs. Discrete Appl. Math. 91, 143–153 (1999)
Klein, S., de Figueiredo, C.M.H.: The NP-completeness of multi-partite cutest testing. Congr. Numer. 119, 216–222 (1996)
Vikas, N.: Computational complexity of graph compaction. In: Proceedings of the tenth ACM-SIAM Symposium on Discrete Algorithms, pp. 977–978 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Figueiredo, C.M.H., Klein, S., Kohayakawa, Y., Reed, B.A. (2000). Finding Skew Partitions Efficiently. In: Gonnet, G.H., Viola, A. (eds) LATIN 2000: Theoretical Informatics. LATIN 2000. Lecture Notes in Computer Science, vol 1776. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10719839_18
Download citation
DOI: https://doi.org/10.1007/10719839_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67306-4
Online ISBN: 978-3-540-46415-0
eBook Packages: Springer Book Archive