Defective coloring
In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph.
In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour.
In defective coloring, on the other hand, the vertices are allowed to have neighbours of the same colour to a certain extent.
Defective coloring was introduced nearly simultaneously by Andrews and Jacobson,[1] Harary and Jones and Cowen, Cowen and Woodall.
[2] Surveys of this and related colorings are given by Marietjie Frick.
[3] Cowen, Cowen and Woodall [2] focused on graphs embedded on surfaces and gave a complete characterization of all k and d such that every planar is (k, d)-colorable.
Together with the (4, 0)-coloring implied by the four color theorem, this solves defective chromatic number for the plane.
Poh [4] and Goddard [5] showed that any planar graph has a special (3,2)-coloring in which each color class is a linear forest, and this can be obtained from a more general result of Woodall.
For general surfaces, it was shown that for each genus
such that every graph on the surface of genus
[2] This was improved to (3, k)-colorable by Dan Archdeacon.
[6] For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times [7][8][9] provides a O(∆E)-time algorithm for defective coloring graphs of maximum degree ∆.
A (k, d)-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer.
Hence, (k, 0)-coloring is equivalent to proper vertex coloring.
[10] The minimum number of colours k required for which G is (k, d)-colourable is called the d-defective chromatic number,
[11] For a graph class G, the defective chromatic number of G is minimum integer k such that for some integer d, every graph in G is (k,d)-colourable.
For example, the defective chromatic number of the class of planar graphs equals 3, since every planar graph is (3,2)-colourable and for every integer d there is a planar graph that is not (2,d)-colourable.
Let c be a vertex-coloring of a graph G. The impropriety of a vertex v of G with respect to the coloring c is the number of neighbours of v that have the same color as v. If the impropriety of v is 0, then v is said to be properly colored.
[2] Let c be a vertex-coloring of a graph G. The impropriety of c is the maximum of the improprieties of all vertices of G. Hence, the impropriety of a proper vertex coloring is 0.
[2] An example of defective colouring of a cycle on five vertices,
The first subfigure is an example of proper vertex colouring or a (k, 0)-coloring.
be a connected outerplanar graph.
Hence, by contracting all the edges mentioned above, we obtain
contains a vertex of degree 3 or more, implying that
[2] Corollary: Every planar graph is (4,2)-colorable.
can be colored blue or red if
[13] Defective coloring is computationally hard.
It is NP-complete to decide if a given graph
[14] An example of an application of defective colouring is the scheduling problem where vertices represent jobs (say users on a computer system), and edges represent conflicts (needing to access one or more of the same files).
Allowing a defect means tolerating some threshold of conflict: each user may find the maximum slowdown incurred for retrieval of data with two conflicting other users on the system acceptable, and with more than two unacceptable.
