Polarity on H-split graphs

arXiv2303.17055MaRDI QIDQ6431357FDOQ6431357

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

Publication date: 29 March 2023

Abstract: Given nonnegative integers, $s$ and $k$, an $(s,k)$-polar partition of a graph $G$ is a partition $(A,B)$ of $V_G$ such that $G[A]$ and $overlineG[B]$ are complete multipartite graphs with at most $s$ and $k$ parts, respectively. If $s$ or $k$ is replaced by $infty$, it means that there is no restriction on the number of parts of $G[A]$ or $overlineG[B]$, respectively. A graph admitting a $(1,1)$-polar partition is usually called a split graph. In this work, we present some results related to $(s,k)$-polar partitions on two graph classes generalizing split graphs. Our main results include efficient algorithms to decide whether a graph on these classes admits an $(s,k)$-polar partition, as well as upper bounds for the order of minimal $(s,k)$-polar obstructions on such graph families for any $s$ and $k$ (even if $s$ or $k$ is $infty$).

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

This page was built for publication: Polarity on $H$-split graphs

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