Fernando Esteban Contreras-Mendoza ; César Hernández-Cruz - $2$-polarity and algorithmic aspects of polarity variants on cograph superclasses

dmtcs:11479 - Discrete Mathematics & Theoretical Computer Science, October 10, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.11479
$2$-polarity and algorithmic aspects of polarity variants on cograph superclassesArticle

Authors: Fernando Esteban Contreras-Mendoza ; César Hernández-Cruz

    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.


    Volume: vol. 26:3
    Section: Graph Theory
    Published on: October 10, 2024
    Accepted on: September 9, 2024
    Submitted on: June 19, 2023
    Keywords: Mathematics - Combinatorics,05C75, 05C15, 05C85, 68R10

    Consultation statistics

    This page has been seen 106 times.
    This article's PDF has been downloaded 54 times.