2-polarity and algorithmic aspects of polarity variants on cograph superclasses

MaRDI QIDQ6413010zbMATH OpenFDO

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

Publication date 5 October 2022

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: 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.

This page was built for publication: $2$-polarity and algorithmic aspects of polarity variants on cograph superclasses

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