In graph theory, a cocoloring of a graph G is an assignment of colors to the vertices such that each color class forms an independent set in G or in the complement 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 graphs, complements of bipartite graphs, and split graphs.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
Color, or colour, is the characteristic of human visual perception described through color categories, with names such as red, orange, yellow, green, blue, or purple. This perception of color derives from the stimulation of cone cells in the human eye by electromagnetic radiation in the visible spectrum. Color categories and physical specifications of color are associated with objects through the wavelength of the light that is reflected from them. This reflection is governed by the object's physical properties such as light absorption, emission spectra, etc.
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets.
As the requirement that each color class be a clique or independent is weaker than the requirement for coloring (in which each color class must be an independent set) and stronger than for 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 of G, and that it is greater than or equal to the subchromatic number of G.
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph.
Cocoloring was named and first studied by Lesniak & Straight (1977). Jørgensen (1995) characterizes critical 3-cochromatic graphs, while Fomin, Kratsch & Novelli (2002) describe algorithms for approximating the cochromatic number of a graph. 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.
