Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a vertex of degree at most 2n-1, thus I can show that G is 2k-1 degenerate and prove this theorem by using a known inequality (Chromatic Number $\leq$ Degeneracy of G + 1). that would suffice because any subgraph of G would also be a union of k forests or less, so G would indeed be 2k-1 degenerate.

However I've had difficulties proving this general fact about graphs made of unions of forests and would appreciate some guidance. I'm not sure what the best approach would be, some traits of trees/forests or something else, was unable to make progress via induction.

Thanks a million!

share|improve this question
    
By union, do you mean no edges between the parts? Because if so then you can say something much stronger: the union of $k$ forests has chromatic number at most 2. –  Eric Stucky Dec 27 '13 at 22:28
    
It's not a disjoint union, just a union, the sets of vertices/edges may intersect, so long as you end up getting the original graph G by union of all the k forests. It is true that every forest can be colored with 2 colors. –  Joshua Dec 27 '13 at 22:31
1  
Go for a stronger result: prove that the union of $k$ bipartite graphs can be $2k$-coloured. –  Chris Godsil Dec 28 '13 at 1:59
    
@ChrisGodsil The union of $k$ bipartite graphs can be $2^k$-colored. This is best possible, seeing as the complete graph on $2^k$ vertices is the union of $k$ bipartite graphs. –  bof Dec 28 '13 at 3:43
    
@ChrisGodsil In fact, a graph is $2^k$-colorable if and only if it's the union of $k$ bipartite graphs. –  bof Dec 28 '13 at 3:51
show 1 more comment

1 Answer 1

Hint. Let $G$ be a graph which is the union of $k$ forests. (By the way, since a subgraph of a forest is a forest, each subgraph of $G$ is also the union of $k$ forests.)
(a) Find an upper bound (in terms of $k$ and $n$) for the size (number of edges) of $G$.
(b) Find an upper bound for the average degree of a vertex in $G$.
(c) Show that $\delta(G)\le2k-1$. ($\delta = $minimum degree.)
(d) Show that $\chi(G)\le2k.$ Use induction on the number of vertices, unless "degeneracy" has been covered. [P.S. Oops, I just noticed that you mentioned degeneracy in your question! I apologize for my careless reading!]

Spoilers:

An $n$-vertex forest has at most $n-1$ edges. Since $G$ has $n$ vertices and is the union of $k$ forests, $G$ has at most $k(n-1)$ edges. Hence the degree-sum of $G$ is at most $2k(n-1)$, and the average degree is at most $\dfrac{2k(n-1)}n=2k-\dfrac{2k}n\lt2k$. Since the average degree is less than $2k$, there must be a vertex of degree less than $2k$. Let $v$ be a vertex of degree less than $2k$. By the induction hypothesis, the graph $G-v$ is $2k$-colorable. Since $v$ is adjacent to at most $2k-1$ vertices in $G-v$, there is at least one color available for $v$.

This argument only applies to a finite graph $G$, but the theorem is also true for infinite graphs; the infinite case follows from the finite case by the De Bruijn–Erdős theorem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.