Editing Graph coloring (section)

== Other colorings ==

=== Ramsey theory ===

{{Main|Ramsey theory}}

An important class of ''improper'' coloring problems is studied in [[Ramsey theory]], where the graph's edges are assigned to colors, and there is no restriction on the colors of incident edges. A simple example is the [[theorem on friends and strangers]], which states that in any coloring of the edges of <math>K_6</math>, the complete graph of six vertices, there will be a monochromatic triangle; often illustrated by saying that any group of six people either has three mutual strangers or three mutual acquaintances. Ramsey theory is concerned with generalisations of this idea to seek regularity amid disorder, finding general conditions for the existence of monochromatic subgraphs with given structure.

=== Modular Coloring ===

Modular coloring is a type of graph coloring in which the color of each vertex is the sum of the colors of its adjacent vertices.

Let {{math|k &ge; 2}} be a number of colors where <math>\mathbb{Z}_k</math> is the set of integers modulo k consisting of the elements (or colors) {{math|0,1,2, ..., k-2, k-1}}. First, we color each vertex in G using the elements of <math>\mathbb{Z}_k</math>, allowing two adjacent vertices to be assigned the same color. In other words, we want c to be a coloring such that c: V(G) &rarr; <math>\mathbb{Z}_k</math> where adjacent vertices can be assigned the same color.

For each vertex v in G, the color sum of {{math|v, &sigma;(v)}}, is the sum of all of the adjacent vertices to v mod k. The color sum of v is denoted by

:{{math|1= &sigma;(v) = &sum;<sub>u &in; N(v)</sub> c(u)}}

where u is an arbitrary vertex in the neighborhood of v, N(v). We then color each vertex with the new coloring determined by the sum of the adjacent vertices. The graph G has a modular k-coloring if, for every pair of adjacent vertices a,b, &sigma;(a) &ne; &sigma;(b). The modular chromatic number of G, mc(G), is the minimum value of k such that there exists a modular k-coloring of G.<

For example, let there be a vertex v adjacent to vertices with the assigned colors 0, 1, 1, and 3 mod 4 (k=4). The color sum would be &sigma;(v) = 0 + 1 + 1+ 3 mod 4 = 5 mod 4 = 1. This would be the new color of vertex v. We would repeat this process for every vertex in G. If two adjacent vertices have equal color sums, G does not have a modulo 4 coloring. If none of the adjacent vertices have equal color sums, G has a modulo 4 coloring.

=== Other colorings ===
{{Col-begin}}
{{Col-break}}
; [[Adjacent-vertex-distinguishing-total coloring]] : A total coloring with the additional restriction that any two adjacent vertices have different color sets
; [[Acyclic coloring]] : Every 2-chromatic subgraph is acyclic
; [[B-coloring]] : a coloring of the vertices where each color class contains a vertex that has a neighbor in all other color classes.
; Bounded Coloring : a coloring in which the number of vertices per color is bounded
; [[Circular coloring]] : Motivated by task systems in which production proceeds in a cyclic way
; [[Cocoloring]] : An improper vertex coloring where every color class induces an independent set or a clique
; [[Complete coloring]] : Every pair of colors appears on at least one edge
; [[Defective coloring]] : An improper vertex coloring where every color class induces a bounded degree subgraph.
; [[Distinguishing coloring]] : An improper vertex coloring that destroys all the symmetries of the graph
; [[Equitable coloring]] : The sizes of color classes differ by at most one
; [[Exact coloring]] : Every pair of colors appears on exactly one edge
; [[Fractional coloring]] : Vertices may have multiple colors, and on each edge the sum of the color parts of each vertex is not greater than one
; [[Hamiltonian coloring]] : Uses the length of the longest path between two vertices, also known as the detour distance
; [[Harmonious coloring]] : Every pair of colors appears on at most one edge
; [[Incidence coloring]]: Each adjacent incidence of vertex and edge is colored with distinct colors
; [[Perfect matching#Connection to Graph Coloring|Inherited vertex coloring]] : A set of vertex colorings induced by perfect matchings of [[Edge_coloring|edge-colored Graphs]].
{{Col-break}}
; [[Interval edge coloring]] : A color of edges meeting in a common vertex must be contiguous
; [[List coloring]]: Each vertex chooses from a list of colors
; [[List edge-coloring]]:Each edge chooses from a list of colors
; [[L(h, k)-coloring|L(''h'', ''k'')-coloring]]: Difference of colors at adjacent vertices is at least ''h'' and difference of colors of vertices at a distance two is at least ''k''. A particular case is [[L(2,1)-coloring]].
; [[Oriented coloring]] : Takes into account orientation of edges of the graph
; [[Path coloring]] : Models a routing problem in graphs
; [[Radio coloring]] : Sum of the distance between the vertices and the difference of their colors is greater than ''k'' + 1, where ''k'' is a positive integer.
; [[Rank coloring]] : If two vertices have the same color ''i'', then every path between them contain a vertex with color greater than ''i''
; [[Subcoloring]] : An improper vertex coloring where every color class induces a union of cliques
; [[Sum coloring]] : The criterion of minimalization is the sum of colors
; [[Star coloring]] : Every 2-chromatic subgraph is a disjoint collection of [[star (graph theory)|stars]]
; [[Strong coloring]] : Every color appears in every partition of equal size exactly once
; [[Strong edge coloring]] : Edges are colored such that each color class induces a matching (equivalent to coloring the square of the line graph)
; [[T-coloring|''T''-coloring]] : Absolute value of the difference between two colors of adjacent vertices must not belong to fixed set ''T''
; [[Total coloring]] :Vertices and edges are colored
; [[Tree-depth|Centered coloring]]: Every connected [[induced subgraph]] has a color that is used exactly once
; [[Monochromatic triangle|Triangle-free edge coloring]]: The edges are colored so that each color class forms a [[triangle-free graph|triangle-free]] subgraph
; [[Weak coloring]] : An improper vertex coloring where every non-isolated node has at least one neighbor with a different color
{{col-end}}
Coloring can also be considered for [[signed graph]]s and [[gain graph]]s.