2017arXiv (Cornell University)Open access

Minimal obstructions to $2$-polar cographs

Pavol Hell, César Hernández‐Cruz, Cláudia Linhares Sales

Open full text 0 citations

Abstract

A graph is a cograph if it is $P_4$-free. A $k$-polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by $A$ is a complete multipartite graph with at most $k$ parts, and the subgraph induced by $B$ is a disjoint union of at most $k$ cliques with no other edges. It is known that $k$-polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed $k$. A concrete family of such forbidden induced subgraphs is known for $k=1$, since $1$-polar graphs are precisely split graphs. For larger $k$ such families are not known, and Ekim, Mahadev, and de Werra explicitely asked for the family for $k=2$. In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves $2$-polarity and also preserves the condition of being a cograph. We do not know such an operation for $k > 2$, nevertheless we believe that the results and methods discussed here will also be useful for higher $k$.

Open-access reader

About this research paper

What this paper is about

A graph is a cograph if it is $P_4$-free. A $k$-polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by $A$ is a complete multipartite graph with at most $k$ parts, and the subgraph induced by $B$ is a disjoint union of at most $k$ cliques with no other edges. It is known that $k$-polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed $k$. A concrete family of such forbidden induced subgraphs is known for $k=1$, since $1$-polar graphs are precisely split graphs. For larger $k$ such families are not known, and Ekim, Mahadev, and de Werra explicitely asked for the family for $k=2$. In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves $2$-polarity and also preserves the condition of being a cograph. We do not know such an operation for $k > 2$, nevertheless we believe that the results and methods discussed here will also be useful for higher $k$.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A graph is a cograph if it is $P_4$-free. A $k$-polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by $A$ is a complete multipartite graph with at most $k$ parts, and the subgraph induced by $B$ is a disjoint union of at most $k$ cliques with no other edges. It is known that $k$-polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed $k$. A concrete family of such forbidden induced subgraphs is known for $k=1$, since $1$-polar graphs are precisely split graphs. For larger $k$ such families are not known, and Ekim, Mahadev, and de Werra explicitely asked for the family for $k=2$. In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves $2$-polarity and also preserves the condition of being a cograph. We do not know such an operation for $k > 2$, nevertheless we believe that the results and methods discussed here will also be useful for higher $k$.

Key concepts: Cograph, Combinatorics, Induced subgraph, Partition (number theory), Disjoint sets, Split graph, Multipartite, Induced path

Related papers

Back to paper searchBrowse research topicsOriginal source
Minimal obstructions to $2$-polar cographs — Research Paper | ScholarLens