Defective coloring

Defective coloring was introduced nearly simultaneously by Andrews and Jacobson,{{cite journal| last1=Andrews|first1=James A.|last2=Jacobson|first2=Michael S.|title=On a generalization of chromatic number| journal=Congr. Numer.|volume=47|pages=33–48| year=1985}} Harary and Jones and Cowen, Cowen and Woodall. Surveys of this and related colorings are given by Marietjie Frick.{{cite book|last1=Frick|first1=Marietjie|title=A Survey of (m,k)-Colorings|chapter=A Survey of (M, k)-Colorings |series=Annals of Discrete Mathematics|date=1993|volume=55|pages=45–57|doi=10.1016/S0167-5060(08)70374-1|isbn=9780444894410}} 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 (k, d)-colorable. Namely, there does not exist a d such that every planar graph is (1, d)- or (2, d)-colorable; there exist planar graphs which are not (3, 1)-colorable, but every planar graph is (3, 2)-colorable. Together with the (4, 0)-coloring implied by the four color theorem, this solves defective chromatic number for the plane. Poh {{cite journal|last1=Poh|first1=K. S.|title=On the linear vertex-arboricity of a planar graph|journal=Journal of Graph Theory|date=March 1990|volume=14|issue=1|pages=73–75|doi=10.1002/jgt.3190140108}} and Goddard {{cite journal|last1=Goddard|first1=Wayne|title=Acyclic colorings of planar graphs|journal=Discrete Mathematics|date=7 Aug 1991|volume=91|issue=1|pages=91–94|doi=10.1016/0012-365X(91)90166-Y|doi-access=free}} 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 $g\; \backslash geq\; 0$, there exists a $k=k(g)$ such that every graph on the surface of genus $g$ is (4, k)-colorable. This was improved to (3, k)-colorable by Dan Archdeacon.{{cite journal|last1=Archdeacon|first1=Dan|author-link= Dan Archdeacon |title=A note on defective colorings of graphs in surfaces|journal=Journal of Graph Theory|date=1987|volume=11|issue=4|pages=517–519|doi=10.1002/jgt.3190110408}}

For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times {{cite journal|last1=Bernardi|first1=Claudio|title=On a theorem about vertex colorings of graphs|journal=Discrete Mathematics|date=March 1987|volume=64|issue=1|pages=95–96|doi=10.1016/0012-365X(87)90243-3|doi-access=free}}{{cite journal|last1=Borodin|first1=O.V|last2=Kostochka|first2=A.V|title=On an upper bound of a graph's chromatic number, depending on the graph's degree and density|journal=Journal of Combinatorial Theory | series=Series B |date=Oct–Dec 1977|volume=23|issue=2–3|pages=247–250|doi=10.1016/0095-8956(77)90037-5|doi-access=free}}{{cite journal|last1=Lawrence|first1=Jim|title=Covering the vertex set of a graph with subgraphs of smaller degree|journal=Discrete Mathematics|date=1978|volume=21|issue=1|pages=61–68|doi=10.1016/0012-365X(78)90147-4|doi-access=free}} 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.{{cite journal | last1 = Cowen | first1 = L. |author1-link= Lenore Cowen | last2 = Goddard | first2 = W. | last3 = Jesurum | first3 = C. E. | year = 1997 | title = Defective coloring revisited | journal = Journal of Graph Theory | volume = 24 | issue = 3| pages = 205–219 | doi = 10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T | citeseerx = 10.1.1.52.3835 }}

The minimum number of colours k required for which G is (k, d)-colourable is called the d-defective chromatic number, $\backslash chi\_d\; (G)$.{{cite journal|last1=Frick|first1=Marietjie|last2=Henning|first2=Michael|title=Extremal results on defective colorings of graphs|journal=Discrete Mathematics|volume=126|issue=1–3|pages=151–158|doi=10.1016/0012-365X(94)90260-7|date=March 1994|doi-access=free}}

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.{{cite journal|first1=L. J.|last1=Cowen|author1-link= Lenore Cowen |first2=R. H.|last2=Cowen|first3=D. R.|last3=Woodall|title=Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency|journal=Journal of Graph Theory|date=3 Oct 2006|volume=10|issue=2|pages=187–195|doi=10.1002/jgt.3190100207}}

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.

File:Example of defective colouring of a cycle on five vertices when d = 0, 1, 2.PNG

An example of defective colouring of a cycle on five vertices, $C\_5$, is as shown in the figure. The first subfigure is an example of proper vertex colouring or a (k, 0)-coloring. The second subfigure is an example of a (k, 1)-coloring and the third subfigure is an example of a (k, 2)-coloring. Note that,

$\backslash chi\_0\; (C\_5)\; =\; \backslash chi\; (C\_5)\; =\; 3$

$\backslash chi\_1\; (C\_5)\; =\; 3$

$\backslash chi\_2\; (C\_n)\; =\; 1;\; \backslash forall\; n\; \backslash in\; \backslash mathbb\{N\}$

• It is enough to consider connected graphs, as a graph G is (k, d)-colourable if and only if every connected component of G is (k, d)-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.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.
• If a graph is (k, d)-colourable, then it is (k′, d′)-colourable for each pair (k′, d′) such that k′ ≥ k and d′≥ d.

Proof: Let $G$ be a connected outerplanar graph. Let $v\_0$ be an arbitrary vertex of $G$. Let $V\_i$ be the set of vertices of $G$ that are at a distance $i$ from $v\_0$. Let $G\_i$ be $\backslash langle\; V\_i\; \backslash rangle$, the subgraph induced by $V\_i$.

Suppose $G\_i$ contains a vertex of degree 3 or more, then it contains $K\_\{1,3\}$ as a subgraph. Then we contract all edges of $V\_0\; \backslash cup\; V\_1\; \backslash cup\; ...\; \backslash cup\; V\_\{i-1\}$ to obtain a new graph $G\text{'}$. It is to be noted that $\backslash langle\; V\_0\; \backslash cup\; V\_1\; \backslash cup\; ...\; \backslash cup\; V\_\{i-1\}\; \backslash rangle$ of $G\text{'}$ is connected as every vertex in $V\_i$ is adjacent to a vertex in $V\_\{i-1\}$. Hence, by contracting all the edges mentioned above, we obtain $G\text{'}$ such that the subgraph $\backslash langle\; V\_0\; \backslash cup\; V\_1\; \backslash cup\; ...\; \backslash cup\; V\_\{i-1\}\; \backslash rangle$ of $G\text{'}$ is replaced by a single vertex that is adjacent to every vertex in $V\_i$. Thus $G\text{'}$ contains $K\_\{2,3\}$ 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 $K\_\{2,3\}$ is outerplanar, a contradiction. Hence no graph $G\_i$ contains a vertex of degree 3 or more, implying that $G$ is (k, 2)-colorable.

No vertex of $V\_i$ is adjacent to any vertex of $V\_\{i-1\}$ or $V\_\{i+1\},\; i\; \backslash geqslant\; 1$, hence the vertices of $V\_i$ can be colored blue if $i$ is odd and red if even. Hence, we have produced a (2,2)-coloring of $G$.

Corollary: Every planar graph is (4,2)-colorable.

This follows as if $G$ is planar then every $G\_i$ (same as above) is outerplanar. Hence every $G\_i$ is (2,2)-colourable. Therefore, each vertex of $V\_i$ can be colored blue or red if $i$ is even and green or yellow if $i$ is odd, hence producing a (4,2)-coloring of $G$.

For every integer $t$ there is an integer $N$ such that every graph $G$ with no $K\_t$ minor is $(t-1,N)$-colourable.{{cite journal|last1=Edwards|first1=Katherine|last2=Kang|first2=Dong Yeap|last3=Kim|first3=Jaehoon|last4=Oum|first4=Sang-il|author-link4= Oum Sang-il|last5=Seymour|first5=Paul|title=A Relative of Hadwiger's Conjecture|journal=SIAM Journal on Discrete Mathematics|date=2015|volume=29|number=4|pages=2385–2388|doi=10.1137/141002177|arxiv=1407.5236|s2cid=12157191 }}

=== Computational complexity ===

Defective coloring is computationally hard. It is NP-complete to decide if a given graph $G$ admits a (3,1)-coloring, even in the case where $G$ is of maximum vertex-degree 6 or planar of maximum vertex-degree 7.{{cite journal|last1 = Angelini|first1 = Patrizio|last2 = Bekos|first2 = Michael|last3 = De Luca|first3 = Felice|last4 = Didimo|first4 = Walter|last5 = Kaufmann|first5 = Michael|last6 =Kobourov|first6 = Stephen|last7 = Montecchiani|first7 = Fabrizio|last8 = Raftopoulou|first8 =Chrysanthi|last9 = Roselli|first9 = Vincenzo|last10 = Symvonis|first10 = Antonios|title = VertexColoring with Defects|journal = Journal of Graph Algorithms and Applications|volume = 21|issue = 3|pages = 313–340|doi = 10.7155/jgaa.00418|year = 2017|doi-access = free}}

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.{{cite journal|first1=L. J.|last1=Cowen|author1-link= Lenore Cowen |first2=W.|last2=Goddard|first3=C. E.|last3=Jesurum|title=Coloring with defect|journal=SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms|date=5 January 1997 |pages=548–557|isbn=9780898713909 |url=http://dl.acm.org/citation.cfm?id=314387}}

{{Reflist}}

{{Refbegin}}

• {{Citation

| last1 = Andrews | first1 = James A.

| last2 = Jacobson | first2 = Michael S.

| title=On a generalization of chromatic number

| journal=Congr. Numer.

| volume=47

| pages=33–48

| year=1985

}}

• {{Citation

| last1 = Eaton | first1 = Nancy J.

| last2 = Hull | first2 = Thomas

| title=Defective list colorings of planar graphs

| journal=Bull. Inst. Combin. Appl

| volume=25

| pages=79–87

| year=1999

| citeseerx = 10.1.1.91.4722

}}

• {{Citation

| last1 = William | first1 = W.

| last2 = Hull | first2 = Thomas

| title=Defective Circular Coloring

| journal=Austr. J. Combinatorics

| volume=26

| pages=21–32

| year=2002

| citeseerx = 10.1.1.91.4722

}}

• {{Citation

|last1 = Frick|first1 = Marietjie

|last2 = Henning|first2 = Michael

|title = Extremal results on defective colorings of graphs

|journal = Discrete Mathematics|volume = 126|issue = 1–3|pages = 151–158|doi = 10.1016/0012-365X(94)90260-7

|date = March 1994

|doi-access = free}}

• {{Citation

|last1 = L. J. Cowen

|last2 = W. Goddard

|last3 = C. E. Jesurum|

title = Coloring with defect|journal = SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

|date = 5 January 1997

|pages = 548–557

|isbn = 9780898713909

|url = http://dl.acm.org/citation.cfm?id=314387

}}

• {{Citation

|last1 = L. J. Cowen

|last2 = R. H. Cowen

|last3 = D. R. Woodall

|title = Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency

|journal = Journal of Graph Theory|date = 3 Oct 2006|volume = 10|issue = 2|pages =187–195

|doi = 10.1002/jgt.3190100207

}}

• {{Citation

|last1 = Archdeacon |first1 = Dan

|title = A note on defective colorings of graphs in surfaces

|journal = Journal of Graph Theory

|date = 1987

|volume = 11|issue = 4|pages = 517–519

|doi=10.1002/jgt.3190110408

}}

• {{Citation

|last1 = Poh|first1 = K. S.

|title = On the linear vertex-arboricity of a planar graph

|journal = Journal of Graph Theory

|date = March 1990|volume = 14|issue = 1

|pages=73–75

|doi = 10.1002/jgt.3190140108

}}

• {{Citation

|last1 = Goddard|first1 = Wayne

|title = Acyclic colorings of planar graphs

|journal = Discrete Mathematics

|date = 7 Aug 1991|volume = 91|issue = 1|pages = 91–94

|doi = 10.1016/0012-365X(91)90166-Y

|doi-access = free

}}

• {{Citation

|last1 = Borodin|first1 = O.V

|last2 = Kostochka|first2 = A.V

|title = On an upper bound of a graph's chromatic number, depending on the graph's degree and density

|journal = Journal of Combinatorial Theory

|series = Series B

|date = Oct–Dec 1977|volume = 23|issue = 2–3|pages = 247–250

|doi = 10.1016/0095-8956(77)90037-5

|doi-access = free

}}

• {{Citation

|last1 = Lawrence|first1 = Jim

|title = Covering the vertex set of a graph with subgraphs of smaller degree

|journal = Discrete Mathematics

|date = 1978|volume = 21|issue = 1|pages = 61–68

|doi = 10.1016/0012-365X(78)90147-4

|doi-access = free

}}

• {{Citation

|last1 = Angelini|first1 = Patrizio

|last2 = Bekos|first2 = Michael

|last3 = De Luca|first3 = Felice

|last4 = Didimo|first4 = Walter

|last5 = Kaufmann|first5 = Michael

|last6 = Kobourov|first6 = Stephen

|last7 = Montecchiani|first7 = Fabrizio

|last8 = Raftopoulou|first8 = Chrysanthi

|last9 = Roselli|first9 = Vincenzo

|last10 = Symvonis|first10 = Antonios

|title = Vertex-Coloring with Defects

|journal = Journal of Graph Algorithms and Applications|volume = 21|issue = 3|pages = 313–340|doi = 10.7155/jgaa.00418

|year = 2017

|doi-access = free}}

{{Refend}}

{{DEFAULTSORT:Defective Coloring}}

Category:Graph coloring

Category:NP-complete problems