Negative results on acyclic improper colorings
Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number $k$ is at most $k2^{k-1}$. We prove that this bound is tight for $k \geq 3$. We also show that some improper and/or acyclic colorings are $\mathrm{NP}$-complete on a class $\mathcal{C}$ of planar gr...
| मुख्य लेखक: | |
|---|---|
| स्वरूप: | लेख |
| भाषा: | English |
| प्रकाशित: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| श्रृंखला: | Discrete Mathematics & Theoretical Computer Science |
| विषय: | |
| ऑनलाइन पहुंच: | https://dmtcs.episciences.org/3441/pdf |