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.
Definitions
Below G denotes a simple graph with non-empty vertex set (non-empty) V(G), edge set E(G) and maximum degree Δ(G).
Definition. An incidence is defined as a pair (v, e) where is an end point of In simple words, one says that vertex v is incident to edge e. Two incidences (v, e) and (u, f) are said to be adjacent or neighboring if one of the following holds: v = u, e ≠ f e = f, v ≠ u e = { v, u}, f = { u, w} and v ≠ w.
Definition. Let I(G) be the set of all incidences of G. An incidence coloring of G is a function that takes distinct values on adjacent incidences (we use the simplified notation c(v, u) is used instead of c((v, e)).) The minimum number of colors needed for the incidence coloring of a graph G is known as the incidence chromatic number or incidence coloring number of G, represented by This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.
History
The concept of incidence coloring was introduced by Brualdi and Massey in 1993 who bounded it in terms of Δ(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
Proposition.
Proof. Let v be the vertex with maximum degree Δ in G. Let be the edges that are incident with the vertex v. Consider We can see that every pair of Δ + 1 incidences, that is, is neighborly. Therefore, these incidences have to be colored using distinct colors.
The bound is attained by trees and complete graphs:
If G is a complete graph with at least two vertices then
If G is a tree with at least two vertices then
The main results were proved by Brualdi and Massey (1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph satisfying
The incidence chromatic number of the complete bipartite graph with m ≥ n ≥ 2, is m + 2. and
Incidence coloring of some graph classes
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 fewest colors. It is found out that ∆(G) + 1 colors are required for incidence coloring of square meshes, honeycomb meshes and hexagonal meshes.
The incidence chromatic number of a square mesh is 5. The incidence chromatic number of a hexagonal mesh is 7. The incidence chromatic number of a honeycomb mesh is 4.
Halin graphs
Chen, Wang and Pang proved that if G is a Halin graph with ∆(G) > 4 then For Halin graphs with ∆(G) = 3 or 4, Jing-Zhe Qu showed to be 5 or 6 respectively. Whether the incidence coloring number of Halin graphs with low degree is Δ(G) + 1 is still an unsolved problem.
Shiu and Sun proved every cubic Halin graph other than has an incidence coloring with Δ(G) + 2 colors. Su, Meng and Guo extended this result to all pseudo-Halin graphs.
If the Halin graph G contains a tree T, then
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 proved this for certain cubic graphs such as Hamiltonian cubic graphs. Based on these results, M. H. Dolama, E. Sopena and X. Zhu (2004) studied the graph classes for which is bounded by ∆(G) + c where c is some fixed constant. A graph is said to be k-generated if for every subgraph H of G, the minimum degree of H is at most k.