Minimal obstructions to ( s , 1 )-polarity in cographs

DOI10.1016/J.DAM.2018.11.028MaRDI QIDQ2184672zbMATH OpenOpenAlexFDO

Authors F. Esteban Contreras-Mendoza, César Hernández-Cruz

Publication date 29 May 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.07856

zbMATH Keywords

cographforbidden subgraph characterizationgeneralized colouringmatrix partitionmonopolar graphpolar graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $k,l$ be nonnegative integers. A graph $G$ is $(k,l)$-polar if its vertex set admits a partition $(A,B)$ such that $A$ induces a complete multipartite graph with at most $k$ parts, and $B$ induces a disjoint union of at most $l$ cliques with no other edges. A graph is a cograph if it does not contain $P_4$ as an induced subgraph. It is known that $(k,l)$-polar cographs can be characterized through a finite family of forbidden induced subgraphs, for any fixed choice of $k$ and $l$. The problem of determining the exact members of such family for $k=2=l$ was posted by Ekim, Mahadev and de Werra, and recently solved by Hell, Linhares-Sales and the second author of this paper. So far, complete lists of such forbidden induced subgraphs are known for $0lek,lle2$; notice that, in particular, $(1,1)$-polar graphs are precisely split graphs. In this paper, we focus on this problem for $(s,1)$-polar cographs. As our main result, we provide a recursive complete characterization of the forbidden induced subgraphs for $(s,1)$-polar cographs, for every non negative integer $s$. Additionally, we show that cographs having an $(s,1)$-partition for some integer $s$ (here $s$ is not fixed) can be characterized by forbidding a family of four graphs.

Recommendations

• Minimal obstructions to ( , k )-polarity in cographs
• Minimal obstructions to 2-polar cographs
• Polar cographs
• Polar cographs
• Polarity of chordal graphs

Cites work

• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Complement reducible graphs
• Corrigendum to ``Polar cographs
• Generalized colouring (matrix partitions) of cographs
• Graph partitions with prescribed patterns
• Graph theory
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Induced subgraphs and well‐quasi‐ordering
• List Partitions
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• Polar cographs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(5)

• Minimal obstructions to ( , k )-polarity in cographs
• Minimal obstructions to 2-polar cographs
• Polar cographs
• Minimal obstructions for polarity, monopolarity, unipolarity and (s,1)-polarity in generalizations of cographs
• On two variants of split graphs: 2-unipolar graph and k-probe-split graph

This page was built for publication: Minimal obstructions to \(( s , 1 )\)-polarity in cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184672)