---
tag: 477J96HAGB
kind: concept
name: Star coloring
aliases: [star-chromatic-number]
sources:
  - wikipedia: en:20933302@r1338634768
    locator: Star coloring
    note: adopted
    mention: wikipedia://en/20933302
    sections: [Summary]
same_as:
  wikidata: Q7601205
  wikipedia: Star coloring
inventory: [94FQ5MG1CX]
---

## Summary

In the mathematical field of graph theory, a **star coloring** of a [[graph|00C0BR7D7H]] $G$ is a (proper) [[vertex coloring|0NCPXH194Y]] in which every [[path|03NAMV1DHJ]] on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the [[induced subgraphs|0EREPBVG2G]] formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by (Grünbaum 1973). The **star chromatic number** $\chi_s(G)$ of $G$ is the fewest colors needed to star color $G$.