patternMinor
What is a guarenteed amount of colors, depending on the graph's arboricity
Viewed 0 times
thegraphwhatamountcolorsguarenteedarboricitydepending
Problem
Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist?
For example, $f(d)=d+1$, because a $d+1$-coloring always exists.
My assumption is that $f(a)=2a$. Because each forest can be colored by $2$ colors (Am I correct?), and by using unique color palleteus, we get a $2a$-coloring.
I would like to ask:
For example, $f(d)=d+1$, because a $d+1$-coloring always exists.
My assumption is that $f(a)=2a$. Because each forest can be colored by $2$ colors (Am I correct?), and by using unique color palleteus, we get a $2a$-coloring.
I would like to ask:
- Is my explanation correct?
- Is there a smaller function (depending only on $a$)?
Solution
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$ vertices ($n = even$) is $n/2$ [link]. Therefore, the function $f(a) = 2a$ is the best possible you can get.
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$ vertices ($n = even$) is $n/2$ [link]. Therefore, the function $f(a) = 2a$ is the best possible you can get.
Context
StackExchange Computer Science Q#141204, answer score: 4
Revisions (0)
No revisions yet.