The chromatic number of a triangle-free graph.

1.5k Views Asked by At

Let $G$ be a triangle-free graph. Prove that $$\chi(G)\leq3\left\lceil\dfrac{\Delta(G)+1}{4}\right\rceil$$

What's the relationship between the chromatic number and the maximum degree of a triangle-free graph $G$. I got a hint that I could apply the Brook's Theorem but I have no clue where to start.

1

There are 1 best solutions below

1
On

Hint: If there exists a partition $V(G)$ into $k$ subsets $V_1,\ldots,V_k$ such that $\chi(G_i)\leq \ell$ for every $i$ (where $G_i$ is the subgraph of $G$ induced by $V_i$), then $\chi(G)\leq \ell k$.