부산대학교 도서관

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).