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

DOI10.1016/J.DAM.2018.11.028zbMATH Open1440.05165arXiv2104.07856OpenAlexW2903764142MaRDI QIDQ2184672FDOQ2184672

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)

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.

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

Recommendations

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

zbMATH Keywords

cographmonopolar graphforbidden subgraph characterizationpolar graphmatrix partitiongeneralized colouring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Minimal obstructions for polarity, monopolarity, unipolarity and $(s,1)$-polarity in generalizations of cographs
• Polar cographs
• Minimal obstructions to \(( \infty , k )\)-polarity in cographs
• Minimal obstructions to 2-polar 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)