Editing Graph coloring (section)

=== Vertex coloring ===

When used without any qualification, a '''coloring''' of a graph almost always refers to a ''proper vertex coloring'', namely a labeling of the graph's vertices with colors such that no two vertices sharing the same [[edge (graph theory)|edge]] have the same color. Since a vertex with a [[loop (graph theory)|loop]] (i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless.

The terminology of using ''colors'' for vertex labels goes back to map coloring. Labels like ''red'' and ''blue'' are only used when the number of colors is small, and normally it is understood that the labels are drawn from the [[integer]]s {{math|{{mset|1, 2, 3, ...}}}}.

{{anchor|Chromatic number}}
A coloring using at most {{mvar|k}} colors is called a (proper) '''{{mvar|k}}-coloring'''. The smallest number of colors needed to color a graph {{mvar|G}} is called its '''chromatic number''', and is often denoted {{math|χ(''G'')}}.<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Chromatic Number |url=https://mathworld.wolfram.com/ChromaticNumber.html |access-date=2025-02-09 |website=mathworld.wolfram.com |language=en}}</ref>  Sometimes {{math|γ(''G'')}} is used, since {{math|χ(''G'')}} is also used to denote the [[Euler characteristic]] of a graph.<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Euler Characteristic |url=https://mathworld.wolfram.com/EulerCharacteristic.html |access-date=2025-02-09 |website=mathworld.wolfram.com |language=en}}</ref> A graph that can be assigned a (proper) {{mvar|k}}-coloring is ''' {{mvar|k}}-colorable''', and it is '''{{mvar|k}}-chromatic''' if its chromatic number is exactly {{mvar|k}}. A subset of vertices assigned to the same color is called a ''color class''; every such class forms an [[Independent set (graph theory)|independent set]]. Thus, a {{mvar|k}}-coloring is the same as a partition of the vertex set into {{mvar|k}} independent sets, and the terms ''{{mvar|k}}-partite'' and ''{{mvar|k}}-colorable'' have the same meaning.