In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a mathematical discipline, 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. More precisely, a (k, d)-coloring of a graph G is a coloring of its vertices with k colours such that each vertex has at most d neighbours having the same colour. Hence, (k, 0)-coloring is equivalent to proper vertex coloring. In graph theoretic terms, each colour class in a proper vertex coloring forms an independent set

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

, while each colour class in a defective coloring forms a subgraph of degree at most d.