Defective coloring

Defective coloring

In graph theory, 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.[1] 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.[2]

Notes

  1. ^ Cowen, L., Goddard, W., and Jesurum, C. E. 1997. Defective coloring revisited. J. Graph Theory 24, 3 (Mar. 1997), 205c219. DOI= http://dx.doi.org/10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T
  2. ^ Cowen, L. J., Goddard, W., and Jesurum, C. E. 1997. Coloring with defect. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana, United States, January 05–07, 1997). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 548–557.

References


Stub icon This combinatorics-related article is a stub. You can help Wikipedia by expanding it.