The Chromatic Number of the Union of Two Forests

Abstract

Let $F$ and $F^{\prime }$ be two forests sharing the same vertex set $V$ such that $|E(F)\cap E(F^{\prime })|=\theta$. By $F\cup F^{\prime }$ we denote the graph on $V$ with edge set $E(F)\cup E(F^{\prime })$. Since both $F$ and $F^{\prime }$ are $2$-colorable, we have $\chi (F\cup F^{\prime })\le 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^{\prime }$ contain a path of length three then the chromatic number of $F\cup F^{\prime }$ is at most three. We will characterize those pairs of forests $F$ and $F^{\prime }$ which both contain a path of length three and for which the chromatic number of $F\cup F^{\prime }$ 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].