Incidence coloring

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.

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}.^[1] The two incidences (v,e) and (u,f) are said to be adjacent if one of the given conditions holds:

v = u, e ≠ f
e = f, v ≠ u
e = {v, u}, f = {u, w} and v ≠ w.

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

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 $\chi_i$ (G). This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.

Incidence coloring of Petersen graph

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 $A_c$ (v) = {c(v,e) : v is an end point of edge e where e belongs to edge set E(G)}. An interval incidence coloring of G is an incidence coloring c of graph G such that for each vertex v in V(G), the set $A_c$ (v) is an interval.^[2]

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

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 $\chi_i$ (G) is given as: $\chi_i$ (G) ≥ Δ(G) + 1.

Proof. Let v be the vertex with maximum degree Δ in G. Let $e_1, e_2, e_3, ..., e_\Delta$ be the edges that are incident with the vertex v. Consider $e_1$ = { v,w }. We can see that every pair of Δ + 1 incidences, that is, ( v, $e_1$ ), ( v, $e_2$ ), ( v, $e_3$ ),......, ( 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.

The main results^[1] were determined and proved by Brualdi and Massey(1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph to meet the quality $\chi_i$ (G) = Δ(G) + 1.

$\chi_i$ (G) = n when G = $K_n$ with n ≥ 2.
Let G be a tree of order n where n ≥ 2. Then, $\chi_i$ (G) = Δ(G) + 1.
For a complete bipartite graph $K_{m,n}$ with m ≥ n ≥ 2, incidence chromatic number is m + 2.
For any graph G, $\chi_i$ (G) ≤ 2Δ(G).
For cycle $C_n$ , incidence chromatic number is at most 4. $\chi_i$ ( $C_{3n}$ ) = 3.

Incidence coloring of some graph classes

Meshes

Several algorithms are introduced to provide incidence coloring of meshes^[5] 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.

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

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 $H^2$ is at most Δ( $T^2$ ) + Δ(T) + 8.^[6] Every cubic Halin graph other than complete graph on 4 vertices satisfies incidence coloring with Δ + 2 colors (Result proved by Shiu and Sun). Su, Meng and Guo extended this result and showed that all pseudo-Halin graphs satisfy incidence coloring conjecture. However, when the incidence coloring number of Halin graphs with low degree is Δ(G) + 1 colors is still an unsolved problem.

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 $\chi_i$ (G) is bounded by ∆(G) + c where c is some fixed constant.^[7] A graph is said to be k-generated if for every subgraph H of G, the minimum degree of H is at most k.

Incidence chromatic number of k-degenerated graphs G is at most ∆(G) + 2k - 1.
Incidence chromatic number of k₄ minor free graphs G is at most ∆(G) + 2 and it form a tight bound.
Incidence chromatic number of a planar graph G is at most ∆(G) + 7.

Outerplanar graphs

Consider an outerplanar graph G. Let vertex v in G be a cut vertex such that G – v is union of graphs $H_1$ and $H_2$ . Let graph $G_1$ be the induced subgraph on vertex v and vertices of $H_1$ ; and graph $G_2$ be the induced subgraph on vertex v and vertices of $H_2$ . Then incidence chromatic number of G is maximum among incidence chromatic number of $G_1, G_2$ and 1 + $d_G$ (v) where $d_G$ (v) is the degree of vertex v in G.

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 k₄-minor-free graphs, they accept a (Δ + 2, 2) – incidence coloring.^[7]^[8] 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^[9] 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) = { $v_0, v_1, v_2, ...., v_{N-1}$ } and edge set E(G) = { $v_iv_j :[i-j]_N$ = 1 or d }, where $[x]_y$ denotes x modulo y, n is number of nodes and d is chord length. These graphs are studied due to its application in communication. Kung-Fu Ding, Kung-Jui Pai and Ro-Yu Wu studied the incidence coloring of chordal rings.^[10] Several algorithms are formulated to find the incidence chromatic number of chordal rings. The major findings are:

$\chi_i$ (CR(N,d)) = 5 if N is multiple of 5 and d is 2 or 3.
$\chi_i$ (CR(N,2)) = 6 if N is not a multiple of 5
$\chi_i$ (CR(N,3)) = 6 if N ≡ 2 (mod 5)

Powers of cycles

Keaitsuda Nakprasit and Kittikorn Nakprasit studied the incidence coloring of powers of cycles. They have proved that $C_n^k$ except for certain cases, satisfies the (Δ + 2) conjecture where k is an integer. It was found out that $\chi_i(C_n^k)$ = 2k + 1 = Δ( ${C_n}^k)$ + 1 when n is divisible by 2k + 1, else $\chi_i(C_n^k)$ = 2k + 2.^[11] If n is divisible by 5, $\chi_i(C_n^2)$ = 5. Otherwise, $\chi_i(C_n^2)$ = 6.^[11] Apart from the powers of cycles, studies have been done on powers of other graphs too.

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 $\gamma$ . Then, $\chi_i$ (G) ≥ $\frac{2m}{n - \gamma}$ .^[12]

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,^[4] the incidence coloring of G is equivalent to proper coloring of the digraph D(G), where 2 distinct arcs $\overrightarrow{u v}$ and $\overrightarrow{x y}$ 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 $\frac{2m}{n - \gamma}$ color classes are required.^[12]

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

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.^[13] The interval incidence coloring number, denoted by $\chi_{ii}$ is the smallest number of colors needed for an interval incidence coloring of G. It is clear that $\chi_{i}$ (G) ≤ $\chi_{ii}$ (G).

The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski. They proved that $\chi_{ii}$ (G) ≤ 2∆(G) for any bipartite graph G.^[14] In case of regular bipartite graphs, this equality holds. Subcubic bipartite graphs admit an interval incidence coloring using four, five or six colors. They have also proved that in linear time, for every bipartite graph with ∆(G) = 4, deciding interval incidence 5-colorability can be performed.

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.^[15] 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 $\frac{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,^[4] Yang has proved that the fractional incidence chromatic number of any graph having maximum degree ∆(G) 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)).

Nordhaus–Gaddum inequality

The Nordhaus–Gaddum inequality has been developed for the incidence chromatic number $\chi_i$ (G) of graph G. Consider a graph G with n vertices such that G ≠ $K_n$ or $\overline{K_n}$ . Let $\overline{G}$ represents the complement graph of G. Then, n +2 ≤ $\chi_i$ (G) + $\chi_{i}(\overline{G})$ ≤ 2n − 1.^[12] These bounds are sharp for all values of n.

Incidence coloring game

Incidence coloring game was first introduced by S. D. Andres.^[16] 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 case of an incidence cannot be colored properly, then Bob wins.
If every incidences of graph is colored properly, Alice wins.

The incidence game chromatic number of a graph G, denoted by $i_g(G)$ , is the least number of colors required for Alice to win in 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 $i_g(G)$ in case of k-degenerate graphs with maximum degree Δ 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.^[16] 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.^[17]

References

1 2 Brualdi R. A.; Massey J. Q.(1993), "Incidence and strong edge colorings of graphs", Discrete Mathematics 122, pp. 51–58
↑ Janczewski, R.; Malafiejska, A.; Malafiejski, M., "Interval Wavelength Assignment in All-optical Star Networks", Parallel Processing and Applied Mathematics, 8th International Conference, PPAM 2009, Wtroclaw, Poland, September 13–16, 2009. Revised Selected Papers Part I (Springer), pp. 11–20, doi:10.1007/978-3-642-14390-8_2, ISBN 978-3-642-14389-2
↑ Algor I., Alon N. (1989); "The star arboricity of graphs", Discrete Mathematics 75, pp. 11-22.
1 2 3 Guiduli B. (1997); "On incidence coloring and star arboricity of graphs", Discrete Mathematics 163, pp. 275-278
↑ Huang, C. I.; Wang, Y. L.; Chung, S. S. (2004), "The Incidence Coloring Numbers of Meshes", Computers and Mathematics with Applications 48, pp. 1643–1649
↑ Wang, S. D.; Cheng, D. L.; Pang, S. C. (2002), "The incidence coloring number of Halin graphs and outerplanar graphs", Discrete Mathematics 256, pp. 397–405
1 2 Hosseini Dolama, M.; Sopena, E.; Zhu, X. (2004), "Incidence coloring of k-generated graphs", Discrete Mathematics 283, pp. 121–128
↑ Wang, S.; Xu, J.; Ma, F.; Xu, C. (2008), "The (Δ+2, 2)-incidence coloring of outerplanar graphs", Progress in Natural Science 18, pp. 575–578.
↑ Arden B.W., Lee H. (1981); "Analysis of Chordal Ring Network", IEEE Transactions on Computers 30, pp. 291-295.
↑ Ding K.F., Pai K.J., Yu R. (1981); "Some Results on the Incidence Coloring Number of Chordal Rings*", The 32nd Workshop on Combinatorial Mathematics and Computation Theory, pp. 89-93.
1 2 Nakprasit , K.; Nakprasit, K. (2012), "Incidence colorings of the powers of cycles", International Journal of Pure and Applied Mathematics 76(1), pp. 143–148
1 2 3 4 Sun, P. K. (2012), "Incidence coloring of regular graphs and complement graphs", Taiwanese Journal of Mathematics 16, No. 6, pp. 2289–2295
↑ Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2015), "Interval incidence graph coloring", Discrete Applied Mathematics 182, pp. 73–83
↑ Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2014), "Interval incidence coloring of bipartite graphs", Discrete Applied Mathematics 166, pp. 131–145
↑ Yang, D (2012), "Fractional incidence coloring and star arboricity of graphs", Ars Combinatoria - Waterloo then Winnipeg 105, pp. 213–224
1 2 Andres, S. D. (2009), "The incidence game chromatic number", Discrete Applied Mathematics 157, pp. 1980–1987
↑ Kim, J. Y. (2011), "The incidence game chromatic number of paths and subgraphs of wheels", Discrete Applied Mathematics 159, pp. 683–694

Additional links

Maydanskiy, M. (2005), "The incidence coloring conjecture for graphs of maximum degree 3", Discrete Mathematics 292, pp. 131–141 .
Hartke, S.G.; Helleloid, G.T. (2012), "Reconstructing a graph from its arc incidence graph", Graphs and Combinatorics, 28(5), pp. 637–652, doi:10.1007/s0037301110737 .
Sun, P. K.; Shiu, W. C. (2012), "Invalid proofs on incidence coloring" (PDF), Discrete Mathematics 54, pp. 107–114 .
Li, D; Liu, M. (2008), "Incidence coloring of the squares of some graphs", Discrete Mathematics 308 (24), pp. 6575–6580 .
Bonamy, M.; Hocquard, H.; Kerdjoudj, S.; Raspaud, A. (2015), "Incidence coloring of graphs with high maximum average degree", Source:arxiv .
Hosseini Dolama, M.; Sopena, E. (2005), "On the maximum average degree and the incidence chromatic number of a graph" (PDF), Discrete Mathematics and Theoretical Computer Science 7, pp. 203–216 .
Shiu, W.C.; Sun, P.K. (2006), "Graphs which are not (∆ + 1)-incidence colorable with erratum to the incidence chromatic number of outerplanar graphs" (PDF), Source:ftp .
Shiu, W.C.; Lam, P.C.P.; Chen, D.L. (2002), "On incidence coloring for some cubic graphs", Discrete Mathematics 252, pp. 259–266, doi:10.1016/S0012365X(01)004575 .
Nakprasit, K.; Nakprasit, K. (2014), "The strong chromatic index of graphs and subdivisions", Discrete Mathematics 317, pp. 75–78 .
Ding, K. F.; Pai, K. J; Chang, J. M.; Tsaur, R. (2015), "Some results of incidence coloring of generalized Petersen graphs", Intelligent Systems and Applications: Proceedings of the International Computer Symposium (ICS) held at Taichung, Taiwan, December 12 14, 2014, doi:10.3233/978-1-61499-484-8-85 .
Liang, L.; Gao, W. (2010), "On fractional incidence chromatic number of generalized theta-graph", Journal of Chongqing Normal University, 27(6), pp. 36–39 .
Shiu, W. C.; Lam, P. C. B.; Chen, D. L. (2002), "Note on incidence coloring for some cubic graphs", Discrete Mathematics 252, pp. 259–266 .
Sun, P. K.; Shiu, W. C. (2012), "Some results on incidence coloring, star arboricity and domination number" (PDF), Australasian Journal of Combinitorics 54, pp. 107–114 .
Wu, J. (2009), "Some results on the incidence coloring number of a graph", Discrete Mathematics, 309(12), pp. 3866–3870 .
Li, X.; Tu, J. (2008), "NP-completeness of 4-incidence colorability of semi-cubic graphs", Discrete Mathematics 308, pp. 1334–1340 .
Pai, K.J.; Chang, J.M.; Wu, R.Y. (2014), "Incidence coloring on hypercubes", Theoretical Computer Science 557, pp. 59–65 .
Pai, K.J.; Chang, J.M.; Wu, R.Y. (2014), "On the Incidence Coloring Number of Folded hypercubes" (PDF), Proceeding of the 18th International Computer Science and Engineering Conference (ICSEC 2014), July 30 - August 1, Khon Kaen, Thailand, pp. 7–11 .
Sopena, É.; Wu, J (2013), "The incidence chromatic number of toroidal grids" (PDF), Discussiones Mathematicae Graph Theory, pp. 315–327 .
Andres, S. D. (2009). "Erratum to: The incidence game chromatic number". Discrete Applied Mathematics 158 (6): 728. doi:10.1016/j.dam.2009.11.017.
Charpentier, C.; Sopena, É. (2015), "The incidence game chromatic number of (a,d)- decomposable graphs", Journal of Discrete Algorithms 31, pp. 14–25 .
Wu, J.; Zhu, X. (2008), "The 6-relaxed game chromatic number of outerplanar graphs", Discrete Mathematics 308 (24), pp. 5974–5980, doi:10.1016/j.disc.2007.11.015 .
Meng, X.; Guo, J.; Su, B. (2012), "Incidence coloring of pseudo Halin graphs", Discrete Mathematics 312, pp. 3276–3282, doi:10.1016/j.disc.2012.07.024 .
Andres, S. D. (2009), "Lightness of digraphs in surfaces and directed game chromatic number", Discrete Mathematics 309 (11), pp. 3564–3579 .
Li, X.; Tu, J. (2008), "NPcompleteness of 4incidence colorability of semicubic graphs", Discrete Mathematics, 308(7), pp. 1334–1340, doi:10.1016/j.disc.2007.03.076 .
Zhu, X. (1999), "The game coloring number of planar graphs", Journal of Combinatorial Theory Series B 75 (2), pp. 245–258, doi:10.1006/jctb.1998.1878 .
Liu, X.; Li, Y. (2005), "The incidence chromatic number of some graph", International Journal of Mathematics and Mathematical Sciences 1, doi:10.1155/IJMMS.2005.803 .
Dong, G.X.; Liu, X.F. (2014), "Incidence Coloring Number of Some Join Graphs", Applied Mechanics and Materials, 602-605, pp. 3185–3188, doi:10.4028/www.scientific.net/AMM.602-605.3185 .