---
tag: 3WBMQNYQS9
kind: concept
name: Acyclic coloring
aliases: [acyclic-chromatic-number]
sources:
  - wikipedia: en:690769@r1369246098
    locator: Acyclic coloring
    note: adopted
    mention: wikipedia://en/690769
    sections: [Summary]
same_as:
  wikidata: Q4677981
  wikipedia: Acyclic coloring
inventory: [BQXNF8KVJP]
---

## Summary

In graph theory, an **acyclic coloring** is a (proper) [[vertex coloring|0NCPXH194Y]] in which every 2-chromatic subgraph is acyclic. The **acyclic chromatic number** $A(G)$ of a [[graph|00C0BR7D7H]] $G$ is the fewest colors needed in any acyclic coloring of $G$.