Incidence coloring
that takes distinct values on adjacent incidences (we use the simplified notation c(v, u) is used instead of c((v, e)).)
This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.
The concept of incidence coloring was introduced by Brualdi and Massey in 1993 who bounded it in terms of Δ(G).
This conjecture was disproved by Guiduli, who showed that incidence coloring concept is a directed star arboricity case,[1] introduced by Alon and Algor.
[2] Chen et al. found the incidence chromatic number of paths, fans, cycles, wheels, complete tripartite graph and adding edge wheels.
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.
The bound is attained by trees and complete graphs: The main results were proved by Brualdi and Massey (1993).
Shiu, Sun and Wu have proposed certain necessary conditions for graph satisfying
Chen, Wang and Pang proved that if G is a Halin graph with ∆(G) > 4 then
Whether the incidence coloring number of Halin graphs with low degree is Δ(G) + 1 is still an unsolved problem.
Su, Meng and Guo extended this result to all pseudo-Halin graphs.
Lam and W.C. Shiu had conjectured that the incidence chromatic number of a cubic graph G is at most ∆(G) + 2.
Based on these results, M. H. Dolama, E. Sopena and X. Zhu (2004) studied the graph classes for which
is the degree of vertex v in G. The incidence chromatic number of an outerplanar graph G is at most ∆(G) + 2.
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[7] 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.
Kung-Fu Ding, Kung-Jui Pai and Ro-Yu Wu studied the incidence coloring of chordal rings.
[8] Several algorithms are formulated to find the incidence chromatic number of chordal rings.
so assume n > 2k + 1 and write: Their results can be summarized as follows:[9] The relation to incidence coloring conjecture is given by the observation that
Form a digraph D(G) from graph G by dividing each edge of G into 2 arcs in opposite directions.
The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski.
They have also proved incidence 5-colorability can be decided in linear time for bipartite graphs with ∆(G) = 4.
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.
[10] These bounds are sharp for all values of n. Incidence coloring game was first introduced by S. D.
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
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.
