New answers tagged

2

Your algorithm is known as greedy coloring, and its properties are well-known. When run on a complete bipartite graph, it always produces a 2-coloring (this is a nice exercise).


2

Your explanation is correct. And, you can not do better than $f(a) = 2a$. For example, take a complete graph on $4$ vertices: $a,b,c,d$. The Arboricity is $2$ since $(a,b), (b,c),$ and $(c,d)$ forms the first tree, and the remaining edges form the second tree. The graph is colorable with exactly four colors. In fact, the Arboricity of a complete graph on $n$ ...


Top 50 recent answers are included