Editing Graph coloring (section)

== Definition and terminology ==
<!--[[Chromatic number]] redirects here-->

[[File:Graph with all three-colourings 2.svg|thumb|right|This graph can be 3-colored in 12 different ways.]]

=== 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.

=== Chromatic polynomial ===
[[File:Chromatic polynomial of all 3-vertex graphs.png|thumb|200px|All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph {{math|''E''{{sub|3}}}} (red) admits a 1-coloring; the complete graph {{math|''K''{{sub|3}}}} (blue) admits a 3-coloring; the other graphs admit a 2-coloring.]]
{{Main|Chromatic polynomial}}

The '''chromatic polynomial''' counts the number of ways a graph can be colored using some of a given number of colors. For example, using three colors, the graph in the adjacent image can be colored in 12 ways. With only two colors, it cannot be colored at all. With four colors, it can be colored in 24 + 4 × 12 = 72 ways: using all four colors, there are 4! = 24 valid colorings (''every'' assignment of four colors to ''any'' 4-vertex graph is a proper coloring); and for every choice of three of the four colors, there are 12 valid 3-colorings. So, for the graph in the example, a table of the number of valid colorings would start like this:
{| class="wikitable" style="background:white; text-align:right;"
|-
!Available colors 
| 1 || 2 || 3 || 4 || ...
|-
!Number of colorings 
| 0 || 0 || 12 || 72 || ...
|}

The chromatic polynomial is a function {{math|''P''(''G'', ''t'')}} that counts the number of {{mvar|t}}-colorings of {{mvar|G}}. As the name indicates, for a given {{mvar|G}} the function is indeed a [[polynomial]] in {{mvar|t}}. For the example graph, {{math|1=''P''(''G'', ''t'') = ''t''(''t'' − 1){{sup|2}}(''t'' − 2)}}, and indeed {{math|1=''P''(''G'', 4) = 72}}.

The chromatic polynomial includes more information about the colorability of {{mvar|G}} than does the chromatic number. Indeed, {{mvar|χ}} is the smallest positive integer that is not a zero of the chromatic polynomial {{math|1=χ(''G'') = min{{brace|''k'' : ''P''(''G'', ''k'') > 0}}}}.

{| class="wikitable" style="background:white;"
|+Chromatic polynomials for certain graphs
|-
! Triangle {{math|''K''{{sub|3}}}} 
| {{math|''t''(''t'' − 1)(''t'' − 2)}}
|-
! [[Complete graph]] {{mvar|K{{sub|n}}}} 
| {{math|''t''(''t'' − 1)(''t'' − 2) ... (''t'' − (''n'' − 1))}}
|-
! [[Tree graph|Tree]] with {{mvar|n}} vertices 
| {{math|''t''(''t'' − 1){{sup|''n''−1}}}}
|-
! [[Cycle graph|Cycle]] {{mvar|C{{sub|n}}}}
| {{math|(''t'' − 1){{sup|''n''}} + (−1){{sup|''n''}}(''t'' − 1)}}
|-
! [[Petersen graph]] 
| {{math|''t''(''t'' − 1)(''t'' − 2)(''t''{{sup|7}} − 12''t''{{sup|6}} + 67''t''{{sup|5}} − 230''t''{{sup|4}} + 529''t''{{sup|3}} − 814''t''{{sup|2}} + 775''t'' − 352)}}
|}

=== Edge coloring ===
{{Main|Edge coloring}}

An '''edge coloring''' of a graph is a  proper coloring of the ''edges'', meaning an assignment of colors to edges so that no vertex is incident to two edges of the same color. An edge coloring with {{mvar|k}} colors is called a {{mvar|k}}-edge-coloring and is equivalent to the problem of partitioning the edge set into {{mvar|k}} [[Matching (graph theory)|matchings]]. The smallest number of colors needed for an edge coloring of a graph {{mvar|G}} is the '''chromatic index''', or '''edge chromatic number''', {{math|''{{prime|χ}}''(''G'')}}. A '''Tait coloring''' is a 3-edge coloring of a [[cubic graph]]. The [[four color theorem]] is equivalent to the assertion that every planar cubic [[bridge (graph theory)|bridgeless]] graph admits a Tait coloring.

=== Total coloring ===
{{Main|Total coloring}}

'''Total coloring''' is a type of coloring on the vertices ''and'' edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its end-vertices are assigned the same color. The total chromatic number {{math|''χ''{{pprime}}(''G'')}} of a graph {{mvar|G}} is the fewest colors needed in any total coloring of {{mvar|G}}.

=== Face coloring ===
For a graph with a strong embedding on a surface, the '''face coloring'''  is the dual of the vertex coloring problem.

=== Tutte's flow theory ===
For a graph ''G'' with a strong embedding on an orientable surface, [[William T. Tutte]]<ref>{{harvtxt|Tutte|1949}}</ref><ref>{{harvtxt|Tutte|1954}}</ref><ref>{{harvtxt|Zhang|1997}}</ref> discovered that if the graph is ''k''-face-colorable then ''G'' admits a nowhere-zero ''k''-flow. The equivalence holds if the surface is sphere.

=== Unlabeled coloring ===
An '''unlabeled coloring''' of a graph is an [[Group action (mathematics)|orbit]] of a coloring under the action of the [[graph automorphism|automorphism group]] of the graph. The colors remain labeled; it is the graph that is unlabeled.
There is an analogue of the [[chromatic polynomial]] which counts the number of unlabeled colorings of a graph from a given finite color set.

If we interpret a coloring of a graph on {{mvar|d}} vertices as a vector in {{tmath|\mathbb{Z}^d}}, the action of an automorphism is a [[permutation]] of the coefficients in the coloring vector.