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 v ∈ V ( G ) {\displaystyle v\in V(G)} is an end point of e ∈ E ( G ) . {\displaystyle e\in E(G).} 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 c : I ( G ) → N {\displaystyle c:I(G)\to \mathbb {N} } 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 χ i ( G ) . {\displaystyle \chi _{i}(G).} 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. χ i ( G ) ≥ Δ ( G ) + 1. {\displaystyle \chi _{i}(G)\geq \Delta (G)+1.}
Proof. Let v be the vertex with maximum degree Δ in G. Let e 1 , e 2 , … , e Δ {\displaystyle e_{1},e_{2},\ldots ,e_{\Delta }} be the edges that are incident with the vertex v. Consider e 1 = { v , w } . {\displaystyle e_{1}=\{v,w\}.} We can see that every pair of Δ + 1 incidences, that is, ( v , e 1 ) , ( v , e 2 ) , … , ( v , e Δ ) , ( w , e 1 ) {\displaystyle (v,e_{1}),(v,e_{2}),\ldots ,(v,e_{\Delta }),(w,e_{1})} 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 χ i ( G ) = Δ ( G ) + 1. {\displaystyle \chi _{i}(G)=\Delta (G)+1.}
If G is a tree with at least two vertices then χ i ( G ) = Δ ( G ) + 1. {\displaystyle \chi _{i}(G)=\Delta (G)+1.}
The main results were proved by Brualdi and Massey (1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph satisfying χ i ( G ) = Δ ( G ) + 1. {\displaystyle \chi _{i}(G)=\Delta (G)+1.}
χ i ( G ) ≤ 2 Δ ( G ) . {\displaystyle \chi _{i}(G)\leq 2\Delta (G).}
The incidence chromatic number of the complete bipartite graph K m , n {\displaystyle K_{m,n}} with m ≥ n ≥ 2, is m + 2.
χ i ( C n ) ≤ 4 {\displaystyle \chi _{i}(C_{n})\leq 4} and χ i ( C 3 n ) = 3. {\displaystyle \chi _{i}(C_{3n})=3.}
… excerpt ends here. Continue reading the full article.
