Editing Graph coloring (section)

=== 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)}}
|}