×

Minimal obstructions to \(( \infty , k )\)-polarity in cographs. (English) Zbl 1466.05140

Summary: A graph is a cograph if it does not contain a 4-vertex path as an induced subgraph. An \(( s , k )\)-polar partition of a graph \(G\) is a partition \(( A , B )\) of its vertex set such that \(A\) induces a complete multipartite graph with at most \(s\) parts, and \(B\) induces the disjoint union of at most \(k\) cliques with no other edges. A graph \(G\) is said to be \(( s , k )\)-polar if it admits an \(( s , k )\)-polar partition. The concepts of \(( s , \infty )\)-, \(( \infty , k )\)-, and \(( \infty , \infty )\)-polar graphs can be analogously defined.
T. Ekim et al. [Discrete Appl. Math. 156, No. 10, 1652–1660 (2008; Zbl 1152.05356)] pioneered in the research on polar cographs, obtaining forbidden induced subgraph characterizations for \(( \infty , \infty )\)-polar cographs, as well as for the union of \(( \infty , 1 )\)- and \(( 1 , \infty )\)-polar cographs. Recently, a recursive procedure for generating the list of cograph minimal \(( s , 1 )\)-polar obstructions for any fixed integer \(s\) was found, as well as the complete list of \(( \infty , 1 )\)-polar obstructions. In addition to these results, complete lists of minimal \(( s , k )\)-polar cograph obstructions are known only for the pair \(( 2 , 2 )\).
In this work we are concerned with the problem of characterizing \(( \infty , k )\)-polar cographs for a fixed \(k\) through a finite family of forbidden induced subgraphs. As our main result, we provide complete lists of forbidden induced subgraphs for the cases \(k = 2\) and \(k = 3\). Additionally, we provide a partial recursive construction for the general case. By considering graph complements, these results extend to \(( s , \infty )\)-polar cographs.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1152.05356
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001
[2] R.S.F. Bravo, L.T. Nogueira, F. Protti, C. Vianna, Minimal obstructions of \(( 2 , 1 )\)-cographs with external restrictions, in: Annals of I ETC - Encontro de Teoria da Computação (CSBC 2016), Porto Alegre, 2016, ISSN 2175-2761 (In Portuguese), http://www.pucrs.br/edipucrs/.
[3] Chernyak, Z. A.; Chernyak, A. A., About recognizing \(( \alpha , \beta )\)-classes of polar graphs, Discrete Math., 62, 133-138 (1986) · Zbl 0606.05058
[4] Churchley, R.; Huang, J., Line-polar graphs: Characterization and recognition, SIAM J. Discret. Math., 25, 3, 1269-1284 (2011) · Zbl 1237.05162
[5] Churchley, R.; Huang, J., On the polarity and monopolarity of graphs, J. Graph Theory, 76, 2, 138-148 (2014) · Zbl 1294.05126
[6] Contreras-Mendoza, F. E.; Hernández-Cruz, C., Minimal obstructions to \(( s , 1 )\)-polarity in cographs, Discrete Appl. Math., 281, 111-117 (2020) · Zbl 1440.05165
[7] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 3, 163-174 (1981) · Zbl 0463.05057
[8] Damaschke, P., Induced subgraphs and well-quasi-ordering, J. Graph Theory, 14, 4, 427-435 (1990) · Zbl 0721.05059
[9] T. Ekim, P. Heggernes, D. Meister, Polar permutation graphs, in: J. Fiala, J. Kratochvíl, M. Miller (Eds.), Combinatorial Algorithms, IWOCA 2009, Lecture Notes in Computer Science, vol. 5874, Springer, Berlin, Heidelberg. · Zbl 1267.05215
[10] Ekim, T.; Hell, P.; Stacho, J.; de Werra, D., Polarity of chordal graphs, Discrete Appl. Math., 156, 13, 2469-2479 (2008) · Zbl 1163.05051
[11] Ekim, T.; Mahadev, N. V.R.; de Werra, D., Polar cographs, Discrete Appl. Math., 156, 1652-1660 (2008) · Zbl 1152.05356
[12] Ekim, T.; Mahadev, N. V.R.; de Werra, D., Corrigendum to “Polar cographs”, Discrete Appl. Math., 156, 158 (2014) · Zbl 1286.05135
[13] Farrugia, A., Vertex-partitioning into fixed additive induced-hereditary properties is \(N P\)-hard, Electron. J. Combin., 11 (2004), #R46 · Zbl 1053.05046
[14] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings (matrix partitions) of cographs, (Graph Theory in Paris (2006), Birkhauser), 149-167 · Zbl 1114.05060
[15] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 3, 449-478 (2003) · Zbl 1029.05143
[16] S. Foldes, P.L. Hammer, Split graphs, in: Proc. 8th Sout-Eastern Conf. on Combinatorics, Graph Theory Computing, 1977, pp. 311-315. · Zbl 0407.05071
[17] Hell, P.; Hernández-Cruz, C.; Linhares-Sales, C., Minimal obstructions to \(2\)-polar cographs, Discrete Appl. Math., 261, 219-228 (2019) · Zbl 1410.05164
[18] Le, V. B.; Nevries, R., Complexity and algorithms for recognizing polar and monopolar graphs, Theoret. Comput. Sci., 528, 1-11 (2014) · Zbl 1283.05219
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.