The Chromatic Number of the Union of Two Forests

Let \(F\) and \(F’\) be two forests sharing the same vertex set \(V\) such that \(|E(F) \cap E(F’)| = \theta\). By \(F \cup F’\) we denote the graph on \(V\) with edge set \(E(F) \cup E(F’)\). Since both \(F\) and \(F’\) are \(2\)-colorable, we have \(\chi(F \cup F’) \leq 4\). In this paper we will investigate forests for which we can actually obtain this upper bound for the chromatic number. It will turn out that if neither \(F\) nor \(F’\) contain a path of length three then the chromatic number of \(F \cup F’\) is at most three. We will characterize those pairs of forests \(F\) and \(F’\) which both contain a path of length three and for which the chromatic number of \(F \cup F’\) is always at most three. In the case where one of the forests contains a path of length three and the other does not contain a path of length three we obtained only partial results. The problem then seems to be similar to a problem of Erdős which recently has been solved by Fleischner [2] using a theorem of Alon [3].