4
$\begingroup$

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:

  1. Is my explanation correct?
  2. Is there a smaller function (depending only on $a$)?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Hi, I do not understand both @Eric_ and yours explanation. To my understanding, in arboricity we partition the edges not the vertices. So each vertex appears in $a$ forests. I agree that each forest is using $2$ colors, but the total amount would be $2^a$, not $2a$ (because each vertex has $2$ possible colors in $a$ different places). Why did you come up with $2a$? $\endgroup$
    – Marik S.
    Jun 12, 2021 at 21:43
  • 2
    $\begingroup$ I will explain my source of confusion: When we refer to partition of a graph into forests, we mean that in each partition all the vertices remain yet only the edges are sometimes included and sometimes not. But in each partition all the vertices are there. Truthfully, each such partition can be colors in $2$ colors. But what is the color of a vertex in the original graph? It should be composed of $a$ different colors it had, one in each forest. So we have a binary vector of length $a$. The total amount of possibilities is $2^a$. $\endgroup$
    – Marik S.
    Jun 13, 2021 at 9:35
  • $\begingroup$ I dont claim $2a$ colors is impossible. I agree with your example. My problem is with @Eric_ explanation for the case of a generic graph $G$ with arboricity $a$, I don't see why his explanation means $2a$ and not $2^a$. $\endgroup$
    – Marik S.
    Jun 13, 2021 at 9:37
  • 3
    $\begingroup$ @MarikS. Let me elaborate Eric's reasoning. Suppose the graph is partitioned into forests: $F_1, \dotsc,F_{a}$. Let $V_1,\dotsc,V_a$ be the vertices $spanned$ by the edges of $F_1,\dotsc,F_a$, respectively. We first color the vertices in $V_1$ with $2$ colors. Then, we color the vertices in $V_2 \setminus V_1$ with $2$ new colors. Then $V_3 \setminus (V_2 \cup V_3)$. with $2$ new colors and so on. This is how we color the original graph with $2a$ different colors. Does this help? $\endgroup$
    – Inuyasha Yagami
    Jun 13, 2021 at 11:50
  • $\begingroup$ Yes, it does. Thanks, this is a nice way to look at it, I was stuck thinking we always color all the vertices. $\endgroup$
    – Marik S.
    Jun 13, 2021 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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