# Cocoloring

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Cocoloring
> Markdown URL: https://mediated.wiki/source/Cocoloring.md
> Source: https://en.wikipedia.org/wiki/Cocoloring
> Source revision: 1152935340
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

[[Image:Cocoloring.svg|400px|right|thumb|Cocoloring with 3 colors (upper left figure):
a [proper](/source/Graph_coloring) 3-coloring of this graph is impossible.
The blue [subgraph](/source/Glossary_of_graph_theory) forms a [clique](/source/Clique_(graph_theory)) (bottom right figure),
while the red and green subgraphs form cliques on the graph's [complement](/source/Glossary_of_graph_theory). ]]

In [graph theory](/source/graph_theory), a '''cocoloring''' of a graph ''G'' is an assignment of [color](/source/color)s to the vertices such that each color class forms an [independent set](/source/Independent_set_(graph_theory)) in ''G'' or in the [complement](/source/Glossary_of_graph_theory) of ''G''. The '''cochromatic number''' z(''G'') of ''G'' is the fewest colors needed in any cocolorings of ''G''. The graphs with cochromatic number 2 are exactly the [bipartite graph](/source/bipartite_graph)s, complements of bipartite graphs, and [split graph](/source/split_graph)s.

As the requirement that each color class be a clique or independent is weaker than the requirement for [coloring](/source/Graph_coloring) (in which each color class must be an independent set) and stronger than for [subcoloring](/source/subcoloring) (in which each color class must be a disjoint union of cliques), it follows that the cochromatic number of ''G'' is less than or equal to the [chromatic number](/source/chromatic_number) of ''G'', and that it is greater than or equal to the subchromatic number of ''G''.

Cocoloring was named and first studied by {{harvtxt|Lesniak|Straight|1977}}. {{harvtxt|Jørgensen|1995}} characterizes critical 3-cochromatic graphs, while {{harvtxt|Fomin|Kratsch|Novelli|2002}} describe algorithms for approximating the cochromatic number of a graph. {{harvtxt|Zverovich|2000}} defines a class of ''perfect cochromatic graphs'', analogous to the definition of perfect graphs via graph coloring, and provides a forbidden subgraph characterization of these graphs.

== References ==
{{refbegin}}
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Kratsch | first2 = Dieter
 | last3 = Novelli | first3 = Jean-Christophe
 | doi = 10.1016/S0020-0190(02)00288-0
 | issue = 5
 | journal = Inf. Process. Lett.
 | pages = 285–290
 | title = Approximating minimum cocolourings
 | volume = 84
 | year = 2002| s2cid = 17733740
 }}.
*{{citation
 | last1 = Gimbel | first1 = John
 | last2 = Straight | first2 = H. Joseph
 | doi = 10.1007/BF01788548
 | issue = 1
 | journal = [Graphs and Combinatorics](/source/Graphs_and_Combinatorics)
 | pages = 255–265
 | title = Some topics in cochromatic theory
 | volume = 3
 | year = 1987| s2cid = 8218390
 }}.
*{{citation
 | last = Jørgensen | first = Leif K.
 | doi = 10.1007/BF01793013
 | issue = 3
 | journal = [Graphs and Combinatorics](/source/Graphs_and_Combinatorics)
 | pages = 263–266
 | title = Critical 3-cochromatic graphs
 | volume = 11
 | year = 1995| s2cid = 38851896
 }}.
*{{citation
 | last1 = Lesniak | first1 = L.
 | last2 = Straight | first2 = H. J.
 | journal = Ars Combinatoria
 | pages = 39–46
 | title = The cochromatic number of a graph
 | volume = 3
 | year = 1977}}.
*{{citation
 | last = Straight | first = H. J.
 | doi = 10.1002/jgt.3190030106
 | issue = 1
 | journal = Journal of Graph Theory
 | pages = 43–51
 | title = Cochromatic number and the genus of a graph
 | volume = 3
 | year = 1979}}.
*{{citation
 | last = Zverovich
 | first = Igor V.
 | publisher = Rutgers University Center for Operations Research
 | series = Research report RRR 16-2000
 | title = Perfect cochromatic graphs
 | url = http://rutcor.rutgers.edu/pub/rrr/reports2000/16.ps
 | year = 2000
 | access-date = 2006-10-16
 | archive-url = https://web.archive.org/web/20160303173528/http://rutcor.rutgers.edu/pub/rrr/reports2000/16.ps
 | archive-date = 2016-03-03
 | url-status = dead
 }}.
{{refend}}

Category:Graph coloring

---
Adapted from the Wikipedia article [Cocoloring](https://en.wikipedia.org/wiki/Cocoloring) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Cocoloring?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.