Incidence coloring

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 ${\displaystyle v\in V(G)}$ is an end point of ${\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.

Examples of adjacent/neighboring incidences. The * above the edge e closest to vertex v denotes incidence (v,e).

Definition. Let I(G) be the set of all incidences of G. An incidence coloring of G is a function ${\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 ${\displaystyle \chi _{i}(G).}$ This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.

Incidence coloring of a Petersen graph

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,[1] introduced by Alon and Algor. His counter example showed that incidence chromatic number is at most Δ(G) + O(log Δ(G)).[2]

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.

Proposition. ${\displaystyle \chi _{i}(G)\geq \Delta (G)+1.}$

Proof. Let v be the vertex with maximum degree Δ in G. Let ${\displaystyle e_{1},e_{2},\ldots ,e_{\Delta }}$ be the edges that are incident with the vertex v. Consider ${\displaystyle e_{1}=\{v,w\}.}$ We can see that every pair of Δ + 1 incidences, that is, ${\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 ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$
• If G is a tree with at least two vertices then ${\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 ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• The incidence chromatic number of the complete bipartite graph ${\displaystyle K_{m,n}}$ with m ≥ n ≥ 2, is m + 2.
• ${\displaystyle \chi _{i}(C_{n})\leq 4}$ and ${\displaystyle \chi _{i}(C_{3n})=3.}$

Proposition.[10] Let G be a simple connected graph of order n, size m and domination number ${\displaystyle \gamma .}$ Then ${\displaystyle \chi _{i}(G)\geq {\tfrac {2m}{n-\gamma }}.}$

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,[2] the incidence coloring of G is equivalent to proper coloring of the digraph D(G), where 2 distinct arcs ${\displaystyle {\overrightarrow {uv}}}$ and ${\displaystyle {\overrightarrow {xy}}}$ are adjacent if one of the following conditions holds: (i) u = x; (ii) v = x or y = u. By the definition of adjacency of arcs, an independent set of arcs in D(G) is a star forest. Therefore, a maximal independent set of arcs is a maximal star forest. This implies that at least ${\displaystyle {\tfrac {2m}{n-\gamma }}}$ color classes are required.[10]

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 ${\displaystyle \chi _{i}(G)=\chi _{i}(G^{2})=r+1}$ if and only if V(G) is a disjoint union of r + 1 dominating sets.[10]

Definition. A finite subset ${\displaystyle A\subset \mathbb {N} }$ is an interval if and only if it contains all the numbers between its minimum and its maximum.

Definition. Let c to be an incidence coloring of G and define

${\displaystyle A_{c}(v)=\{c(v,e):(v,e)\in I(G)\}.}$

An interval incidence coloring of G is an incidence coloring c such that for each vertex v of G the set ${\displaystyle A_{c}(v)}$ is an interval.[11][12] 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 ${\displaystyle \chi _{ii}.}$ It is clear that ${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).}$ If only ${\displaystyle \chi _{ii}}$ colors are used for the interval incidence coloring, then it is said to be minimal.

The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski. They proved ${\displaystyle \chi _{ii}(G)\leq \Delta (G)}$ for bipartite graphs.[13] In case of regular bipartite graphs equality holds. Subcubic bipartite graphs admit an interval incidence coloring using four, five or six colors. They have also proved incidence 5-colorability can be decided in linear time for bipartite graphs with ∆(G) = 4.

The fractional version of the incidence coloring was first introduced by Yang in 2007. An 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 adjacent incidences are given disjoint sets of colors.[14] 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 ${\displaystyle {\tfrac {k}{r}}}$ in such a way that G admits a r-tuple incidence k-coloring. Fractional incidence coloring has great applications in several fields of computer science. Based on incidence coloring results by Guiduli,[2] Yang has proved that the fractional incidence chromatic number of any graph is at most Δ(G) + 20 log Δ(G) + 84. He has also proved the existence of graphs with fractional incidence chromatic number at least Δ(G) + Ω(log Δ(G)).

Let G be a graph with n vertices such that ${\displaystyle G\neq K_{n},{\overline {K_{n}}}}$ where ${\displaystyle {\overline {G}}}$ denotes the complement of G. Then ${\displaystyle n+2\leq \chi _{i}(G)+\chi _{i}({\overline {G}})\leq 2n-1.}$[10] These bounds are sharp for all values of n.

Incidence coloring game was first introduced by S. D. Andres.[15] 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:

• Alice and Bob color the incidences of a graph G with a set k of colors.
• They are taking turns to provide a proper coloring to an uncolored incidence. Generally, Alice begins.
• In the case of an incidence that cannot be colored properly, then Bob wins.
• If every incidences of the graph is colored properly, Alice wins.

The incidence game chromatic number of a graph G, denoted by ${\displaystyle i_{g}(G)}$, is the fewest colors required for Alice to win in an incidence coloring game. It unifies the ideas of incidence chromatic number of a graph and game chromatic number in case of an undirected graph. Andres found out that the upper bound for ${\displaystyle i_{g}(G)}$ in case of k-degenerate graphs is 2Δ + 4k − 2. This bound was improved to 2Δ + 3k − 1 in case of graphs in which Δ is at least 5k. The incidence game chromatic number of stars, cycles, and sufficiently large wheels are also determined.[15] John Y. Kim (2011) has found out the exact incidence game chromatic number of large paths and has given a correct proof of a result stated by Andres concerning the exact incidence game chromatic number of large wheels.[16]