The chromatic number of a triangle-free graph. 
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. 
 A: First take a partition of $V$ into $k=\lceil(\Delta+1)/4\rceil$ classes $V_1,\dots,V_k$ that minimizes the number of monochromatic edges. Note $\Delta<4k.$ By the pigeonhole principle, for each vertex $v\in V_j,$ there is some class $V_i$ such that at most three of the at most $\Delta$ neighbors of $v$ lie in $V_i.$ By minimality, putting $v$ in $V_i$ instead of $V_j$ cannot decrease the number of monochromatic edges, so $v$ has at most three neighbors in $V_j.$ In other words $\Delta(G[V_j])\leq 3$ for each $j.$
By Brooks' theorem and the triangle-free assumption, each $G[V_j]$ has a 3-coloring. Using disjoint color sets for each $V_j$ we get a $3k$-coloring of $G$ as required.
A history of this result is given in the introduction to "Chromatic number, girth and maximal degree" by B. Bollobás. Improving the bound is an open problem.
A: 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$.
