Skip to main content
added 1 character in body
Source Link
David Wood
  • 1.3k
  • 9
  • 12

Corollary 3 in https://dmtcs.episciences.org/344 says that for every graph $G$, if $G'$ is the 1-subdivision of $G$, then the acyclic chromatic number of $G$$G'$ is at least $\sqrt{\frac12 \chi(G)}$. Apply this result with $G$ the complete graph $K_n$. Then the acyclic chromatic number of $K'_n$ is at least $\sqrt{\frac12 n}$. Since $K'_n$ is 2-degenerate, the acyclic chromatic number of 2-degenerate graphs is unbounded.

Corollary 3 in https://dmtcs.episciences.org/344 says that for every graph $G$, if $G'$ is the 1-subdivision of $G$, then the acyclic chromatic number of $G$ is at least $\sqrt{\frac12 \chi(G)}$. Apply this result with $G$ the complete graph $K_n$. Then the acyclic chromatic number of $K'_n$ is at least $\sqrt{\frac12 n}$. Since $K'_n$ is 2-degenerate, the acyclic chromatic number of 2-degenerate graphs is unbounded.

Corollary 3 in https://dmtcs.episciences.org/344 says that for every graph $G$, if $G'$ is the 1-subdivision of $G$, then the acyclic chromatic number of $G'$ is at least $\sqrt{\frac12 \chi(G)}$. Apply this result with $G$ the complete graph $K_n$. Then the acyclic chromatic number of $K'_n$ is at least $\sqrt{\frac12 n}$. Since $K'_n$ is 2-degenerate, the acyclic chromatic number of 2-degenerate graphs is unbounded.

Source Link
David Wood
  • 1.3k
  • 9
  • 12

Corollary 3 in https://dmtcs.episciences.org/344 says that for every graph $G$, if $G'$ is the 1-subdivision of $G$, then the acyclic chromatic number of $G$ is at least $\sqrt{\frac12 \chi(G)}$. Apply this result with $G$ the complete graph $K_n$. Then the acyclic chromatic number of $K'_n$ is at least $\sqrt{\frac12 n}$. Since $K'_n$ is 2-degenerate, the acyclic chromatic number of 2-degenerate graphs is unbounded.