$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929541766709248 |
|---|---|
| author | Contreras-Mendoza, Fernando Esteban Hernández-Cruz, César |
| author_facet | Contreras-Mendoza, Fernando Esteban Hernández-Cruz, César |
| contents | A graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs. Polar graphs and monopolar graphs are defined as $(\infty, \infty)$- and $(1, \infty)$-polar graphs, respectively, and unipolar graphs are those graphs with a polar partition $(A, B)$ such that $A$ is a clique.
The problems of deciding whether an arbitrary graph is a polar graph or a monopolar graph are known to be NP-complete. In contrast, deciding whether a graph is a unipolar graph can be done in polynomial time. In this work we prove that the three previous problems can be solved in linear time on the classes of $P_4$-sparse and $P_4$-extendible graphs, generalizing analogous results previously known for cographs.
Additionally, we provide finite forbidden subgraph characterizations for $(2,2)$-polar graphs on $P_4$-sparse and $P_4$-extendible graphs, also generalizing analogous results recently obtained for the class of cographs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_02497 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | $2$-polarity and algorithmic aspects of polarity variants on cograph superclasses Contreras-Mendoza, Fernando Esteban Hernández-Cruz, César Combinatorics 05C75, 05C15, 05C85, 68R10 A graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs. Polar graphs and monopolar graphs are defined as $(\infty, \infty)$- and $(1, \infty)$-polar graphs, respectively, and unipolar graphs are those graphs with a polar partition $(A, B)$ such that $A$ is a clique. The problems of deciding whether an arbitrary graph is a polar graph or a monopolar graph are known to be NP-complete. In contrast, deciding whether a graph is a unipolar graph can be done in polynomial time. In this work we prove that the three previous problems can be solved in linear time on the classes of $P_4$-sparse and $P_4$-extendible graphs, generalizing analogous results previously known for cographs. Additionally, we provide finite forbidden subgraph characterizations for $(2,2)$-polar graphs on $P_4$-sparse and $P_4$-extendible graphs, also generalizing analogous results recently obtained for the class of cographs. |
| title | $2$-polarity and algorithmic aspects of polarity variants on cograph superclasses |
| topic | Combinatorics 05C75, 05C15, 05C85, 68R10 |
| url | https://arxiv.org/abs/2210.02497 |