KOR

e-Article

Partitioning $P_4$-tidy graphs into a stable set and a forest.
Document Type
Journal
Author
Bravo, Raquel (BR-UFF-IC) AMS Author Profile; Oliveira, Rodolfo (BR-UFF4-IED) AMS Author Profile; da Silva Junior, Fábio (BR-UFF-IC) AMS Author Profile; Souza, Uéverton S. (BR-UFF-IC) AMS Author Profile
Source
Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences (Discrete Appl. Math.) (20230101), 338, 22-29. ISSN: 0166-218X (print).eISSN: 1872-6771.
Subject
05 Combinatorics -- 05C Graph theory
  05C69 Dominating sets, independent sets, cliques
Language
English
ISSN
18726771
Abstract
A graph $G$ is near-bipartite if it admits a partition$(\Cal{S},\Cal{F})$ of $V(G)$ into two subsets $\Cal{S}$ and $\Cal{F}$,in which $\Cal{S}$ is a stable set, and $\Cal{F}$ induces a forest (anacyclic subgraph) in $G$.\par The near-bipartiteness problem of determining whether a graph has anear-bipartition is $\ssf{NP}$-complete even when restricted to graphs withmaximum degree four, perfect graphs, graphs with diameter three, linegraphs, and planar graphs. The problem is, however, polynomial-timesolvable on cographs, graphs of diameter at most two, and $P_5$-freegraphs.\par Given a graph $G$ and a vertex set $P$ inducing a $P_4$ in $G$, avertex $v$ is said to be a partner of $P$ if $v\in V(G)\setminus P$ and$G[P\cup\{v\}]$ has at least two $P_4$'s. The graph is $P_4$-tidy ifany $P_4$ has at most one partner.\par The main result of this paper is characterization of near-bipartite$P_4$-tidy graphs by forbidden induced subgraphs, namely $K_4$,$I_2+I_2+I_2$ and $W_5$. The authors also present a characterization ofa $P_4$-tidy graph that admits a partition of its vertex set into astable set and a tree (a connected and acyclic subgraph).