Defective coloring

Last updated

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)

Contents

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 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 , there exists a such that every graph on the surface of genus is (4, k)-colorable. [1] This was improved to (3, k)-colorable by Dan 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, . [10]

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. [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 Example of defective colouring of a cycle on five vertices when d = 0, 1, 2.PNG
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, , 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,

Properties

Some results

Every outerplanar graph is (2,2)-colorable

Proof: Let be a connected outerplanar graph. Let be an arbitrary vertex of . Let be the set of vertices of that are at a distance from . Let be , the subgraph induced by . Suppose contains a vertex of degree 3 or more, then it contains as a subgraph. Then we contract all edges of to obtain a new graph . It is to be noted that of is connected as every vertex in is adjacent to a vertex in . Hence, by contracting all the edges mentioned above, we obtain such that the subgraph of is replaced by a single vertex that is adjacent to every vertex in . Thus contains 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 is outerplanar, a contradiction. Hence no graph contains a vertex of degree 3 or more, implying that is (k, 2)-colorable. No vertex of is adjacent to any vertex of or , hence the vertices of can be colored blue if is odd and red if even. Hence, we have produced a (2,2)-coloring of . [1]

Corollary: Every planar graph is (4,2)-colorable. This follows as if is planar then every (same as above) is outerplanar. Hence every is (2,2)-colourable. Therefore, each vertex of can be colored blue or red if is even and green or yellow if is odd, hence producing a (4,2)-coloring of .

Graphs excluding a complete minor

For every integer there is an integer such that every graph with no minor is -colourable. [12]

Computational complexity

Defective coloring is computationally hard. It is NP-complete to decide if a given graph admits a (3,1)-coloring, even in the case where is of maximum vertex-degree 6 or planar of maximum vertex-degree 7. [13]

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

Notes

  1. 1 2 3 4 5 6 7 8 Cowen, L. J.; Cowen, R. H.; Woodall, D. R. (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". A Survey of (m,k)-Colorings. Annals of Discrete Mathematics. Vol. 55. pp. 45–57. doi:10.1016/S0167-5060(08)70374-1. ISBN   9780444894410.
  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". 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". Journal of Graph Theory. 24 (3): 205–219. CiteSeerX   10.1.1.52.3835 . doi:10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T.
  10. Frick, Marietjie; Henning, Michael (March 1994). "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 0507, 1997). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 548–557.
  12. Edwards, Katherine; Kang, Dong Yeap; Kim, Jaehoon; Oum, Sang-il; Seymour, Paul (2015). "A Relative of Hadwiger's Conjecture". SIAM Journal on Discrete Mathematics. 29 (4): 2385–2388. arXiv: 1407.5236 . doi:10.1137/141002177. S2CID   12157191.
  13. Angelini, Patrizio; Bekos, Michael; De Luca, Felice; Didimo, Walter; Kaufmann, Michael; Kobourov, Stephen; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Roselli, Vincenzo; Symvonis, Antonios (2017). "VertexColoring with Defects". Journal of Graph Algorithms and Applications. 21 (3): 313–340. doi: 10.7155/jgaa.00418 .
  14. Cowen, L. J.; Goddard, W.; Jesurum, C. E. (5 January 1997). "Coloring with defect". SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms: 548–557. ISBN   9780898713909.

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v.

<span class="mw-page-title-main">Triangle-free graph</span> Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

<span class="mw-page-title-main">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

<span class="mw-page-title-main">Greedy coloring</span> One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.

<span class="mw-page-title-main">Grinberg's theorem</span> On Hamiltonian cycles in planar graphs

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Gallai–Hasse–Roy–Vitaver theorem</span> Duality of graph colorings and orientations

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

The Earth–Moon problem is an unsolved problem on graph coloring in mathematics. It is an extension of the planar map coloring problem, and was posed by Gerhard Ringel in 1959. An intuitive form of the problem asks how many colors are needed to color political maps of the Earth and Moon, in a hypothetical future where each Earth country has a Moon colony which must be given the same color. In mathematical terms, it seeks the chromatic number of biplanar graphs. It is known that this number is at least 9 and at most 12.

References