Perfect Forests in Graphs and Their Extensions

Gregory Gutin, Anders Yeo

Research output: Contribution to journalArticlepeer-review

18 Downloads (Pure)


Let $G$ be a graph on $n$ vertices. For $i\in \{0,1\}$, a spanning forest $F$ of $G$ is called
an $i$-perfect forest if every tree in $F$ is an induced subgraph of $G$ and exactly $i$ vertices of $F$ have even degree (including zero).
An $i$-perfect forest of $G$ is proper if it has no vertices of degree zero. Scott (2001) showed that
every connected graph with an even number of vertices contains a (proper) 0-perfect forest.
We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges.
Moreover, we show that to decide whether $G$ has a 0-perfect forest with at least $n/2+k$ edges, where $k$ is the parameter, is W[1]-hard.
We also prove that for a prescribed edge $e$ of $G,$ it is NP-hard to obtain a 0-perfect forest containing $e,$ but one can decide if there exists
a 0-perfect forest not containing $e$ in polynomial time.
It is easy to see that every connected graph with an odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests.
We give a characterization of when a connected graph has a proper 1-perfect forest.
Original languageEnglish
JournalJournal of Graph Theory
Issue number3
Early online date9 May 2022
Publication statusPublished - 2022

Cite this