Defective coloring

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. (See here for Glossary of graph theory)

History

Defective coloring was introduced nearly simultaneously by Burr and Jacobson, Harary and Jones and Cowen, Cowen and Woodall.[1] Surveys of this and related colorings are given by Marietjie Frick.[2] Cowen, Cowen and Woodall [1] 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 [3] and Goddard [4] showed that any planar graph has a special (3,2)-coloring in ehich 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 \geq 0, there exists a k=k(g) such that every graph on the surface of genus g is (4, k)-colorable.[1] This was improved to (3, k)-colorable by Archdeacon.[5] For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times [6][7][8] 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.[9]

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, \chi_d (G).[10]

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.[1]

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.[1]

Example

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, 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,

\chi_0 (C_5) = \chi (C_5) = 3

\chi_1 (C_5) = 3

\chi_2 (C_n) = 1; \forall n \in \mathbb{N}

Properties

Few Results

Every outerplanar graph is (2,2)-colorable

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 \langle V_i \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 \cup V_1 \cup ... \cup V_{i-1} to obtain a new graph G'. It is to be noted that \langle V_0 \cup V_1 \cup ... \cup V_{i-1} \rangle of G' 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' such that the subgraph \langle V_0 \cup V_1 \cup ... \cup V_{i-1} \rangle of G' is replaced by a single vertex that is adjacent to every vertex in V_i. Thus G' 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. It should also be noted that no vertex of V_i is adjacent to any vertex of V_{i-1} or V_{i+1}, i \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.[1]

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.

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.[12]

Notes

  1. 1 2 3 4 5 6 7 8 L. J. Cowen; R. H. Cowen; D. R. Woodall (3 Oct 2006). "Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency". Journal of Graph Theory 10 (2): 187–195. doi:10.1002/jgt.3190100207.
  2. ↑ Frick, Marietjie (1993). "A Survey of (m,k)-Colorings". Annals of Discrete Mathematics 55: 45–57. doi:10.1016/S0167-5060(08)70374-1.
  3. ↑ Poh, K. S. (March 1990). "On the linear vertex-arboricity of a planar graph". Journal of Graph Theory 14 (1): 73–75. doi:10.1002/jgt.3190140108.
  4. ↑ Goddard, Wayne (7 Aug 1991). "Acyclic colorings of planar graphs". Journal Discrete Mathematics 91 (1): 91–94. doi:10.1016/0012-365X(91)90166-Y.
  5. ↑ Archdeacon, Dan (1987). "A note on defective colorings of graphs in surfaces". Journal of Graph Theory 11 (4): 517–519. doi:10.1002/jgt.3190110408.
  6. ↑ Bernardi, Claudio (March 1987). "On a theorem about vertex colorings of graphs". Discrete Mathematics 64 (1): 95–96. doi:10.1016/0012-365X(87)90243-3.
  7. ↑ Borodin, O.V; Kostochka, A.V (Oct–Dec 1977). "On an upper bound of a graph's chromatic number, depending on the graph's degree and density". Journal of Combinatorial Theory, Series B 23 (2-3): 247–250. doi:10.1016/0095-8956(77)90037-5.
  8. ↑ Lawrence, Jim (1978). "Covering the vertex set of a graph with subgraphs of smaller degree". Discrete Mathematics 21 (1): 61–68. doi:10.1016/0012-365X(78)90147-4.
  9. ↑ Cowen, L.; Goddard, W.; Jesurum, C. E. (1997). "Defective coloring revisited". J. Graph Theory 24 (3): 205–219. doi:10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T.
  10. ↑ Frick, Marietjie; Henning, Michael. "Extremal results on defective colorings of graphs". Discrete Mathematics 126 (1-3): 151–158. doi:10.1016/0012-365X(94)90260-7.
  11. ↑ 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.
  12. ↑ L. J. Cowen; W. Goddard; C. E. Jesurum. "Coloring with defect". SODA '97 Proceedings of the eighth annual ACM-SIAM symposium on discrete algorithms: 548–557.

References

This article is issued from Wikipedia - version of the Friday, October 30, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.