![]() | ||
In graph theory, coloring generally implies assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where in each incidence of an edge with a vertex is assigned a color under certain constraints.
Contents
- Definitions
- History
- Basic results
- Meshes
- Halin graphs
- k degenerated graphs
- Outerplanar graphs
- Chordal rings
- Powers of cycles
- Relation between incidence chromatic number and domination number of a graph
- Interval incidence coloring
- Fractional incidence coloring
- NordhausGaddum inequality
- Incidence coloring game
- References
Definitions
Let G = (V, E) be a simple graph with vertex set (non-empty) V(G) and edge set E(G). An incidence is defined as a pair (v, e) where v ϵ V(G) is an end point of e ϵ E(G). In simple words, one says that vertex v is incident to edge e.
Consider a set of incidences, say, I(G) = {(v,e) : v ϵ V(G) and e ϵ E(G) and v ϵ e}. The two incidences (v,e) and (u,f) are said to be adjacent if one of the given conditions holds:
An incidence coloring of G can be defined as a function c: I(G) → N such that c((v, e)) ≠ c((u,f)) for any incidences (v, e) and (u, f) that are adjacent. This implies that incidence coloring assigns distinct colors to neighborly incidences. [Generally, a simplified notation c(v, u) is used instead of c((v, e)).]
The minimum number of colors needed for incidence coloring of a graph is known as incidence chromatic number or incidence coloring number of G, represented by
Let A be a finite subset of N, the set of natural numbers. A is an interval if and only if it contains all the numbers between minimum of A and maximum of A. Consider c to be an incidence coloring of graph G. Let
The interval incidence coloring number of G is the minimum number of colors used for the interval incidence coloring of G. It is denoted by IIC(G). If only IIC(G) colors are used for the interval incidence coloring, then it is said to be minimal.
History
The concept of incidence coloring was introduced by Brualdi and Massey in 1993. They bounded it in terms of Δ(G), the maximum degree of a graph G. Initially, the incidence chromatic number of trees, complete bipartite graphs and complete graphs was found out. They also conjectured that all graphs can have an incidence coloring using Δ(G) + 2 colors (Incidence coloring conjecture - ICC). This conjecture was disproved by Guiduli, who showed that incidence coloring concept is a directed star arboricity case, introduced by Alon and Algor. His counter example showed that incidence chromatic number is at most Δ(G) + O(log Δ(G)).
Chen et al. found the incidence chromatic number of paths, fans, cycles, wheels, complete tripartite graph and adding edge wheels. Few years later, Shiu et al. showed that this conjecture is true for certain cubic graphs such as cubic Hamiltonian graphs. He showed that in case of outerplanar graph of maximum degree 4, the incidence chromatic number is not 5. The bounds for incidence chromatic number of various graph classes is found out now.
Basic results
Consider a graph G with maximum degree Δ(G). The trivial lower bound for
Proof. Let v be the vertex with maximum degree Δ in G. Let
The bound is attained by trees and complete graphs.
The main results were determined and proved by Brualdi and Massey(1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph to meet the quality
Meshes
Several algorithms are introduced to provide incidence coloring of meshes like square meshes, honeycomb meshes and hexagonal meshes. These algorithms are optimal. For each mesh, the incidence colors can be made in the linear time with the least number of colors. It is found out that Δ(G) + 1 colors are required for incidence coloring of square meshes, honeycomb meshes and hexagonal meshes.
Halin graphs
For a Halin graph G with maximum degree greater than 4, the incidence chromatic number is Δ(G) + 1; which was proved by Chen, Wang and Pang. In case of Halin graphs with Δ(G) = 3 or 4, Jing-Zhe Qu determined that the incidence chromatic number to be 5 or 6 respectively. If Halin graph G contains a tree T, then incidence chromatic number of
k-degenerated graphs
D.L. Chen, P.C.B. Lam and W.C. Shiu had conjectured that the incidence chromatic number of a cubic graph G is at most ∆(G)+2. They even proved that it is true in case of certain cubic graphs such as class of Hamiltonian cubic graphs. Based on these results, M. H. Dolama, E. Sopena and X. Zhu (2004) studied the graph classes for which
Outerplanar graphs
Consider an outerplanar graph G. Let vertex v in G be a cut vertex such that G – v is union of graphs
The incidence chromatic number of an outerplanar graph G is at most Δ(G) + 2 where Δ(G) is maximum degree of G. In case of outerplanar graphs with Δ(G) greater than 3, the incidence chromatic number is Δ(G) +1.
Since outerplanar graphs are k4-minor-free graphs, they accept a (Δ + 2, 2) – incidence coloring. The solution for incidence chromatic number of the outerplanar graph G having Δ(G) = 3 and 2-connected outerplanar graph is still an open question.
Chordal rings
Chordal rings are variations of ring networks. The use of chordal rings in communication is very extensive due to its advantages over the interconnection networks with ring topology and other analysed structures such as meshes, hypercubes, Cayley's graphs, etc. Arden and Lee first proposed the chordal ring of degree 3, that is, the ring structured network in which every node has an extra link known as chord, to some other node in the network. Distributed loop networks are chordal rings of degree 4 which is constructed by adding 2 extra chords at every vertex in a ring network.
Chordal rings, denoted by CR(N,d) is a graph with vertex set V(G) = {
Powers of cycles
Keaitsuda Nakprasit and Kittikorn Nakprasit studied the incidence coloring of powers of cycles. They have proved that
Relation between incidence chromatic number and domination number of a graph
Consider a simple connected graph G with order n, size m and domination number
Proof. Form a digraph D(G) from graph G by dividing each edge of G into 2 arcs in opposite directions. We can see that the total number of arcs in D(G) is 2m. According to Guiduli, the incidence coloring of G is equivalent to proper coloring of the digraph D(G), where 2 distinct arcs
This relation has been widely used in the characterization of (r+1)-incidence colorable r-regular graphs. The major result on incidence coloring of r-regular graphs is: If graph G is r-regular graph, then
Interval incidence coloring
The interval incidence coloring of graph G is an incidence coloring of G such that the set of colors given for the incidences adjoining the same vertex forms an interval. The interval incidence coloring number, denoted by
The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski. They proved that
Fractional incidence coloring
The fractional version of the incidence coloring was first introduced by Yang in 2007. A r-tuple incidence k-coloring of a graph G is the assignment of r colors to each incidence of graph G from a set of k colors such that the neighboring (adjacent) incidences are given disjoint sets of colors. By definition, it is obvious that 1-tuple incidence k-coloring is an incidence k-coloring too.
The fractional incidence chromatic number of graph G is the infimum of the fractions
Nordhaus–Gaddum inequality
The Nordhaus–Gaddum inequality has been developed for the incidence chromatic number
Incidence coloring game
Incidence coloring game was first introduced by S. D. Andres. It is the incidence version of the vertex coloring game, in which the incidences of a graph are colored instead of vertices. Incidence game chromatic number is the new parameter defined as a game-theoretic analogous of the incidence chromatic number.
The game is that two players, Alice and Bob construct a proper incidence coloring. The rules are stated below:
The incidence game chromatic number of a graph G, denoted by