부산대학교 도서관

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 (an acyclic subgraph) in $G$. \par The near-bipartiteness problem of determining whether a graph has a near-bipartition is $\ssf{NP}$-complete even when restricted to graphs with maximum degree four, perfect graphs, graphs with diameter three, line graphs, and planar graphs. The problem is, however, polynomial-time solvable on cographs, graphs of diameter at most two, and $P_5$-free graphs. \par Given a graph $G$ and a vertex set $P$ inducing a $P_4$ in $G$, a vertex $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 if any $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 of a $P_4$-tidy graph that admits a partition of its vertex set into a stable set and a tree (a connected and acyclic subgraph).