acyclic chromatic number

tags: coloring

equivalent to: acyclic chromatic number

providers: ISGCI

Relations

Results

• 2019 The Graph Parameter Hierarchy by Sorge
  • page 3 : acyclic chromatic number – The \emph{acyclic chromatic number} of a graph $G = (V,E)$ is the smallest size of a vertex partition $P={V_1,\dots,V_\ell}$ such that each $V_i$ is an independent set and for all $V_i,V_j$ the graph $G[V_i \cup V_j]$ does not contain a cycle.
  • page 8 : maximum degree upper bounds acyclic chromatic number by a polynomial function – Lemma 4.6 ([15]). The acyclic chromatic number $\chi_a$ is uppre bounded by the maximum degree $\Delta$ (for every graph with $\Delta > 4$). We have $\chi_a \le \Delta(\Delta-1)/2$.
  • page 8 : h-index upper bounds acyclic chromatic number by a polynomial function – Lemma 4.7. The acyclic chromatic number $\chi_a$ is upper bounded by the $h$-index $h$. We have $\chi_a \le h(h+1)/2$.
  • page 8 : genus upper bounds acyclic chromatic number by a linear function – Lemma 4.8 ([3]). The accylic chromatic number $\chi_a$ is upper bounded by the genus $g$. We have $\chi_a \le 4g+4$.
  • page 8 : acyclic chromatic number upper bounds boxicity by a polynomial function – Lemma 4.9. The boxicity $b$ is upper bounded by the acyclic chromatic number $\chi_a$ (for every graph with $\chi_a>1$). We have $b \le \chi_a(\chi_a-1)$.
  • page 9 : acyclic chromatic number upper bounds degeneracy by a polynomial function – Lemma 4.18. The acyclic chromatic number $a$ upper bounds the degeneracy $d$. We have $d \le 2 \binom a2 - 1$
• 2004 Track Layouts of Graphs by Dujmović, Pór, Wood
  • page 14 : book thickness upper bounds acyclic chromatic number by an exponential function – Theorem 5. Acyclic chromatic number is bounded by stack-number (ed: a.k.a. book-thickness). In particular, every $k$-stack graph $G$ has acyclich chromatic number $\chi_a(G) \le 80^{k(2k-1)}$.
• https://en.wikipedia.org/wiki/Acyclic_coloring
  • acyclic chromatic number – … an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic.
• unknown source
  • acyclic chromatic number upper bounds boxicity by a computable function
  • book thickness upper bounds acyclic chromatic number by a computable function
• https://www.graphclasses.org/classes/par_31.html
  • acyclic chromatic number – The acyclic chromatic number of a graph $G$ is the smallest size of a vertex partition $V_1,\dots,V_\ell$ such that each $V_i$ is an independent set and for all $i,j$ that graph $G[V_i \cup V_j]$ does not contain a cycle.