{{short description|Graph coloring with an allowed number of same-color neighbors}} {{see also|Glossary of graph theory}} 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, the vertices are allowed to have neighbours of the same colour to a certain extent.
==History== Defective coloring was introduced nearly simultaneously by Andrews and Jacobson,<ref name="andrewsCN47">{{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}}</ref> Harary and Jones and Cowen, Cowen and Woodall.<ref name="Defective_colorings_of_graphs_in_surfaces"/> Surveys of this and related colorings are given by Marietjie Frick.<ref name=Frick_survey>{{cite book|last1=Frick|first1=Marietjie|title=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}}</ref> Cowen, Cowen and Woodall <ref name="Defective_colorings_of_graphs_in_surfaces"/> 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 <ref name=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}}</ref> and Goddard <ref>{{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}}</ref> 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 <math>g \geq 0</math>, there exists a <math>k=k(g)</math> such that every graph on the surface of genus <math>g</math> is (4, ''k'')-colorable.<ref name="Defective_colorings_of_graphs_in_surfaces"/> This was improved to (3, ''k'')-colorable by Dan Archdeacon.<ref name=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}}</ref> For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times <ref>{{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}}</ref><ref>{{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}}</ref><ref>{{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}}</ref> provides a ''O(∆E)''-time algorithm for defective coloring graphs of maximum degree ∆.
==Definitions and terminology==
===Defective coloring=== 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.<ref>{{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 }}</ref>
===''d''-defective chromatic number=== The minimum number of colours ''k'' required for which ''G'' is (''k'', ''d'')-colourable is called the ''' ''d''-defective chromatic number''', <math>\chi_d (G)</math>.<ref name=chromatic_number>{{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}}</ref>
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.
===Impropriety of a vertex=== 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.<ref name=Defective_colorings_of_graphs_in_surfaces>{{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}}</ref>
===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.<ref name="Defective_colorings_of_graphs_in_surfaces"/>
==Example== thumb|Example of defective colouring of a cycle on five vertices when d = 0, 1, 2 An example of defective colouring of a cycle on five vertices, <math>C_5</math>, 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,
<math>\chi_0 (C_5) = \chi (C_5) = 3</math>
<math> \chi_1 (C_5) = 3</math>
<math>\chi_2 (C_n) = 1; \forall n \in \mathbb{N} </math>
==Properties==
* 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.<ref name="Defective_colorings_of_graphs_in_surfaces"/> *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''.<ref>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.</ref> *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''.<ref name="Defective_colorings_of_graphs_in_surfaces"/>
==Some results==
=== Every outerplanar graph is (2,2)-colorable=== '''Proof:''' Let <math>G</math> be a connected outerplanar graph. Let <math>v_0</math> be an arbitrary vertex of <math>G</math>. Let <math>V_i</math> be the set of vertices of <math>G</math> that are at a distance <math>i</math> from <math>v_0</math>. Let <math>G_i</math> be <math>\langle V_i \rangle</math>, the subgraph induced by <math>V_i</math>. Suppose <math>G_i</math> contains a vertex of degree 3 or more, then it contains <math>K_{1,3}</math> as a subgraph. Then we contract all edges of <math>V_0 \cup V_1 \cup ... \cup V_{i-1}</math> to obtain a new graph <math>G'</math>.
<math>\langle V_0 \cup V_1 \cup ... \cup V_{i-1} \rangle</math> of <math>G'</math> is connected as every vertex in <math>V_i</math> is adjacent to a vertex in <math>V_{i-1}</math>. Hence, by contracting all the edges mentioned above, we obtain <math>G'</math> such that the subgraph <math>\langle V_0 \cup V_1 \cup ... \cup V_{i-1} \rangle</math> of <math>G'</math> is replaced by a single vertex that is adjacent to every vertex in <math>V_i</math>. Thus <math>G'</math> contains <math>K_{2,3}</math> 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 <math>K_{2,3}</math> is outerplanar, a contradiction. Hence no graph <math>G_i</math> contains a vertex of degree 3 or more, implying that <math>G</math> is ('''k''', 2)-colorable. No vertex of <math>V_i</math> is adjacent to any vertex of <math>V_{i-1}</math> or <math>V_{i+1}, i \geqslant 1</math>, hence the vertices of <math>V_i</math> can be colored blue if <math>i</math> is odd and red if even. Hence, we have produced a (2,2)-coloring of <math>G</math>.<ref name="Defective_colorings_of_graphs_in_surfaces" />
'''Corollary: Every planar graph is (4,2)-colorable.''' This follows as if <math>G</math> is planar then every <math>G_i</math> (same as above) is outerplanar. Hence every <math>G_i</math> is (2,2)-colourable. Therefore, each vertex of <math>V_i</math> can be colored blue or red if <math>i</math> is even and green or yellow if <math>i</math> is odd, hence producing a (4,2)-coloring of <math>G</math>.
=== Graphs excluding a complete minor === For every integer <math>t</math> there is an integer <math>N</math> such that every graph <math>G</math> with no <math>K_t</math> minor is <math>(t-1,N)</math>-colourable.<ref name="relative_Hadwiger">{{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 }}</ref>
=== Computational complexity === Defective coloring is computationally hard. It is NP-complete to decide if a given graph <math>G</math> admits a (3,1)-coloring, even in the case where <math>G</math> is of maximum vertex-degree 6 or planar of maximum vertex-degree 7.<ref name="relative_Angelini">{{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}}</ref>
==Applications== 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.<ref name=Cowen_Goddard_Jesurum>{{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}}</ref>
==Notes== {{Reflist}}
==References== {{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