In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. 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, vertices are allowed to have neighbours of the same colour to a certain extent.
History
Defective coloring was introduced nearly simultaneously by Burr and Jacobson, Harary and Jones and Cowen, Cowen and Woodall. Surveys of this and related colorings are given by Marietjie Frick. Cowen, Cowen and Woodall focused on graphs embedded on surfaces and gave a complete characterization of all k and d such that every planar is -colorable. Namely, there does not exist a d such that every planar graph is - or -colorable; there existplanar graphs which are not -colorable, but every planar graph is -colorable. Together with the -coloring implied by the four color theorem, this solves defective chromatic number for the plane. Poh and Goddard showed that any planar graph has a special -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, there exists a such that every graph on the surface of genus is -colorable. This was improved to -colorable by Dan Archdeacon. For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times provides a O-time algorithm for defective coloring graphs of maximum degree ∆.
Definitions and terminology
Defective coloring
A -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 and d to be a non-negative integer. Hence, -coloring is equivalent to proper vertex coloring.
''d''-defective chromatic number
The minimum number of colours k required for which G is -colourable is called the d-defective chromatic number,.. 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 -colourable. For example, the defective chromatic number of the class of planar graphs equals 4, since every planar graph is -colourable and for every integer d there is a planar graph that is not -colourable.
Impropriety of a vertex
Let c be a vertex-coloring of a graph G. The impropriety of a vertex v of Gwith 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.
Impropriety of a vertex-coloring
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.
Example
An example of defective colouring of a cycle on five vertices,, is as shown in the figure. The first subfigure is an example of proper vertex colouring or a -coloring. The second subfigure is an example of a -coloring and the third subfigure is an example of a -coloring. Note that,
Properties
It is enough to consider connected graphs, as a graph G is -colourable if and only if every connected component of G is -colourable.
In graph theoretic terms, each colour class in a proper vertex coloring forms an independent set, while each colour class in a defective coloring forms a subgraph of degree at most d.
If a graph is -colourable, then it is -colourable for each pair such that k′ ≥ k and d′≥ d.
Proof: Let be a connected outerplanar graph. Let be an arbitrary vertex of. Let be the set of vertices of that are at a distance from. Let be, the subgraph induced by. Suppose contains a vertex of degree 3 or more, then it contains as a subgraph. Then we contract all edges of to obtain a new graph. It is to be noted that of is connected as every vertex in is adjacent to a vertex in. Hence, by contracting all the edges mentioned above, we obtain such that the subgraph of is replaced by a single vertex that is adjacent to every vertex in. Thus contains as a subgraph. But every subgraph of an outerplanar graph is outerplanar and every graph obtained by contracting edges of an outerplanar graph is outerplanar. This implies that is outerplanar, a contradiction. Hence no graph contains a vertex of degree 3 or more, implying that is -colorable. No vertex of is adjacent to any vertex of or, hence the vertices of can be colored blue if is odd and red if even. Hence, we have produced a -coloring of. Corollary: Every planar graph is -colorable. This follows as if is planar then every is outerplanar. Hence every is -colourable. Therefore, each vertex of can be colored blue or red if is even and green or yellow if is odd, hence producing a -coloring of.
Graphs excluding a complete minor
For every integer there is an integer such that every graph with no minor is -colourable.
Computational complexity
Defective coloring is computationally hard. It is NP-complete to decide if a given graph admits a -coloring, even in the case where is of maximum vertex-degree 6 or planar of maximum vertex-degree 7.
Applications
An example of an application of defective colouring is the scheduling problem where vertices represent jobs, and edges represent conflicts. 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.
