<p>While I know nothing about these measures, quick googling led me to the paper</p>
<p>Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, André Kündgen, Radhika Ramamurthi: <em>Coloring with no <span class="math-container">$2$</span>-colored <span class="math-container">$P_4$</span>’s</em>, Electronic Journal of Combinatorics 11 (2004), no. 1, art. no. R26, doi: <a href="https://doi.org/10.37236/1779" rel="noreferrer">10.37236/1779</a>.</p>
<p>They prove that <span class="math-container">$\chi_s(G)\le\chi_a(G)\bigl(2\chi_a(G)-1\bigr)$</span> (Corollary 4.6), and exhibit a family of graphs <span class="math-container">$G_t$</span> such that <span class="math-container">$\chi_a(G_t)=t$</span> and <span class="math-container">$\chi_s(G_t)=\binom{t+1}2$</span> (Theorem 6.3 and the comment below).</p>

CC BY-SA 4.0
2021-06-11T10:22:11.050Z
Thanks. Interestingly, the graphs $G_t$ they construct are $(t-1)$-degenerate.
Cyriac Antony
CC BY-SA 4.0
2021-06-11T09:23:18.753Z
2021-06-11T09:23:18.753Z
Emil Jeřábek
<p><strong>Is <span class="math-container">$\chi_s(G)-\chi_a(G)$</span> unbounded in general graphs?</strong></p>
<p>I thought <span class="math-container">$\chi_s(G)-\chi_a(G)$</span>, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general graphs. But, I am unable to show this. I think I have seen a paper on star coloring which give <span class="math-container">$\chi_a$</span>-binding functions for the star chromatic number and claim that these functions are best possible (but I don't recall the name of the paper; I think the paper dealt with a number of colouring variants including acyclic coloring and star coloring). If this is true, then <span class="math-container">$\chi_s(G)-\chi_a(G)$</span> must be unbounded.</p>
<p><strong>Definitions</strong><br />
A coloring of a graph <span class="math-container">$G$</span> is a function <span class="math-container">$f$</span> from the vertex set of <span class="math-container">$G$</span> to a set of colors such that <span class="math-container">$f(u)\neq f(v)$</span> for every edge <span class="math-container">$uv$</span> of <span class="math-container">$G$</span>. A coloring <span class="math-container">$f$</span> of <span class="math-container">$G$</span> is an <em>acyclic coloring</em> if there is no cycle in <span class="math-container">$G$</span> 2-colored by <span class="math-container">$f$</span>. A coloring <span class="math-container">$f$</span> of <span class="math-container">$G$</span> is a star coloring if there is no 4-vertex path in <span class="math-container">$G$</span> 2-colored by <span class="math-container">$f$</span>. The acyclic chromatic number <span class="math-container">$\chi_a(G)$</span> (resp. the star chromatic number <span class="math-container">$\chi_s(G)$</span>) is the minimum number of colors required to acyclic color (resp. star color) the graph <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2021-06-11T06:46:03.613Z
If you stumble on a paper discussing $\chi_a$-binding functions for the star chromatic number, the name of that paper would be enough for an answer.
Cyriac Antony
<graph-theory><graph-colouring>
Is the difference between the acyclic chromatic number and the star chromatic number unbounded?
Cyriac Antony
# Is the difference between the acyclic chromatic number and the star chromatic number unbounded?

(Asked by: username_0 on 2021-06-11)

**Is $\chi\_s(G)-\chi\_a(G)$ unbounded in general graphs?**

I thought $\chi\_s(G)-\chi\_a(G)$, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general graphs. But, I am unable to show this. I think I have seen a paper on star coloring which give $\chi\_a$-binding functions for the star chromatic number and claim that these functions are best possible (but I don't recall the name of the paper; I think the paper dealt with a number of colouring variants including acyclic coloring and star coloring). If this is true, then $\chi\_s(G)-\chi\_a(G)$ must be unbounded.

**Definitions**  
A coloring of a graph $G$ is a function $f$ from the vertex set of $G$ to a set of colors such that $f(u)\neq f(v)$ for every edge $uv$ of $G$. A coloring $f$ of $G$ is an *acyclic coloring* if there is no cycle in $G$ 2-colored by $f$. A coloring $f$ of $G$ is a star coloring if there is no 4-vertex path in $G$ 2-colored by $f$. The acyclic chromatic number $\chi\_a(G)$ (resp. the star chromatic number $\chi\_s(G)$) is the minimum number of colors required to acyclic color (resp. star color) the graph $G$.

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_0**: If you stumble on a paper discussing $\chi_a$-binding functions for the star chromatic number, the name of that paper would be enough for an answer.  

---

## 1 answers

### Answer by username_1 on 2021-06-11. Score: 6 | Accepted answer

While I know nothing about these measures, quick googling led me to the paper

Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, André Kündgen, Radhika Ramamurthi: *Coloring with no $2$-colored $P\_4$’s*, Electronic Journal of Combinatorics 11 (2004), no. 1, art. no. R26, doi: [10.37236/1779](https://doi.org/10.37236/1779).

They prove that $\chi\_s(G)\le\chi\_a(G)\bigl(2\chi\_a(G)-1\bigr)$ (Corollary 4.6), and exhibit a family of graphs $G\_t$ such that $\chi\_a(G\_t)=t$ and $\chi\_s(G\_t)=\binom{t+1}2$ (Theorem 6.3 and the comment below).

> **Comments:**
> **username_0**: Thanks. Interestingly, the graphs $G_t$ they construct are $(t-1)$-degenerate.  

---

