2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Cyriac Antony Jun 11 at 6:46
5
$\begingroup$

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.

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).

$\endgroup$
1
  • $\begingroup$ Thanks. Interestingly, the graphs $G_t$ they construct are $(t-1)$-degenerate. $\endgroup$ – Cyriac Antony Jun 11 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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