The Incidence Coloring Page

This page is maintained by Éric Sopena and is intended to collect results on incidence colorings that have been published in refereed journals or conferences.
If you have any suggestion, or new result not mentioned here, please do not hesitate to contact me at eric.sopena@labri.fr.

Definitions and notation

Definitions

An incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident with v. Two incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G then assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors. The smallest number of colors required for such a coloring is called the incidence chromatic number (or, sometimes, the incidence coloring number) of G, and is denoted by Χi(G). The notion of incidence coloring was introduced in 1993 by Brualdi and Massey (BM93).

Example

Figure (a) besides shows the set of incidences, denoted {a, b, …, h}, of the cycle C4 on four vertices {u, v, w, x}. The incidence a corresponds to the pair (u,uv), while the incidence b corresponds to the pair (v,vu). An incidence coloring of C4 using 4 colors is depicted in figure (b). (It can easily be checked that the incidences of C4 cannot be colored by using only 3 colors.)

Notation

For every graph G, we denote by V(G) its vertex set, by E(G) its edge set, by I(G) its set of incidences and by Δ(G) its maximum degree. We denote by deg(v) the degree of a vertex v. The incidence chromatic number of a graph G is denoted by Χi(G). Let v be a vertex in G. We denote by A+(v) the set of incidences of the form (u,uv) and by A-(v) the set of incidences of the form (v,vu). Observe that both A+(v) and A-(v) contain exactly deg(v) incidences.

(k,p)-incidence colorings

An incidence coloring of a graph G using k colors is an incidence (k,p)-coloring of G if for every vertex v in V(G), the number of colors used for coloring A+(v) is at most p. We denote by Χi,p(G) the smallest number of colors required for an incidence (k,p)-coloring of G. Observe that Χi(G) ≤ Χi,p(G) for every graph G and every p ≥ 1.

Let IG(G) be the undirected graph whose vertices are the incidences of I(G) and edges are those pairs of incidences that are adjacent in G. The graph IG(G) is the incidence graph of G. An incidence k-coloring of G is then nothing but a proper vertex k-coloring of IG(G).
Let H be the bipartite graph defined by V(H) = V(G) ∪ E(G) and E(H) = { (v,e) / vV(G), eE(G), e and v are incident in G }. Each edge of E(H) corresponds to an incidence of I(G) and, therefore, an incidence coloring of G corresponds to a strong edge coloring of H (that is a proper coloring of the edges of E(H) such that each color class is an induced matching in H). (See Brualdi and Massey (BM93) for more details.)
Let now G be an undirected graph and G* be the digraph obtained from G by replacing each edge of E(G) by two opposite arcs. Any incidence (v,e) of I(G), with e = vw, can then be associated with the arc vw in A(G*). Therefore, an incidence coloring of G can be viewed as an arc-coloring of G* satisfying (i) any two arcs having the same source vertex (of the form uv and uw) are assigned distinct colors and (ii) any two consecutive arcs (of the form uv and vw) are assigned distinct colors. Hence, for every color c, the subgraph of G* induced by the arcs with color c is a forest of directed stars, whose arcs are directed towards the center. The incidence chromatic number of G therefore corresponds to the directed star-arboricity of G*, as introduced by Algor and Alon in (AA89). (See Guiduli (Gu97) for more details.)
Finally, if f is a (k,1)-incidence coloring of an undirected graph G, then for every vertex v in V(G), the set { f(u,uv), u,vV(G) } has cardinality 1. Therefore, the mapping c defined by c(v) = f(u,uv) for every vertex v is well-defined. Moreover, it is not difficult to see that c(u) ≠ c(v) for every two vertices u and v whose distance in G is 1 or 2. Therefore, c is a proper vertex-coloring of the square G2 of G. Conversely, from every proper k-vertex-coloring of G2, we obtain an incidence (k,1)-coloring f of G (and, thus, a k-incidence coloring of G) by setting f(u,uv) = c(v) for every incidence (u,uv) of G. Therefore, Χi,1(G) = Χ(G2) and Χi(G) ≤ Χ(G2) for every graph G.

General results

Complexity

Li and Tu proved in (LT08) that computing the incidence chromatic number of a graph is NP-hard. In (HH12), Hartke and Helleloid proposed a linear algorithm which, given an undirected graph H, determines whether H is the incidence graph of some undirected graph G and, if the answer is yes, returns the corresponding graph G.

General lower bound

Let G be a graph with at least one edge and v be any vertex in V(G). Since, in any incidence coloring of G, all the incidences of A+(v) are (i) pairwise adjacent and (ii) adjacent to every incidence in A-(v), we get that Χi(G) ≥ Δ(G) + 1 for every graph G. This bound is tight and is attained, for instance, by complete graphs and trees (see below). Some necessary conditions for a graph G to satisfy the condition Χi(G) = Δ(G) + 1 have been proposed by Shiu and Sun (SS08) and by Wu (Wu09).

General upper bounds

Let G be a graph. The mapping f from I(G) to V(G) that assigns to every incidence (v,vu) the vertex u is obviously an incidence coloring of G. Therefore, Χi(G) ≤ |V(G)| for every graph G. (More precisely, this coloring is a (|V(G)|,1)-incidence coloring of G since f(A+(v)) = {v} for every vertex v in V(G).)
The general bound Χi(G) ≤ 2.Δ(G) for every graph G has been proved by Brualdi and Massey (BM93) and extended to multigraphs by Nakprasit and Nakprasit (NN14). This bound has been improved by Guiduli (Gu97) who proved that Χi(G) ≤ Δ(G) + 20.log Δ(G) + 84 for every graph G.
Recall that the star arboricity of an undirected graph G is the smallest number of star forests needed to cover G. In (Ya12, written in 2007), Yang observed the following: let G be an undirected graph with star arboricity st(G), let s : E(G) → {1, …, st(G) } be a mapping such that s-1(i) is a forest of stars for every i, 1 ≤ ist(G), and let λ be a proper edge coloring of G. Now define the mapping f by f(u,uv) = s(uv) if v is the center of a star in some forest s-1(i) (if some star is reduced to one edge, we arbitrarily choose one of its end vertices as the center) and f(u,uv) = λ(uv) otherwise. It is not difficult to check that f is indeed an incidence coloring of G. Therefore, thanks to the classical Vizing’s result, the relation Χi(G) ≤ Δ(G) + st(G) (resp. Χi(G) ≤ Δ(G) + st(G) + 1) holds for every graph of class 1 (resp. of class 2). (Recall that the chromatic index Χ’(G) of any graph G is either Δ(G) (such graphs are said to be of class 1) or Δ(G) + 1 (such graphs are said to be of class 2)).

In (Su12), Sun established the following Nordhaus-Gaddum-type inequality: for every graph G with n vertices, GKn, GcKn, n + 2 ≤ Χi(G) + Χi(Gc) ≤ 2n - 1, where Gc stands for the complement of G. Sun also proved that both these bounds are sharp for every n.

The “(Δ + 2)-conjecture”

In (BM93), Brualdi and Massey conjectured that the relation Χi(G) ≤ Δ(G) + 2 holds for every graph G. This was disproved by Guiduli in (Gu97) who showed that Paley graphs have incidence chromatic number at least Δ + Ω(log Δ). However, this inequality seems to hold for many of the commonly considered graph classes and several papers are devoted to the proof of this fact.

Simple graph classes

Here are several results concerning the incidence chromatic number of simple graph classes.

Paths and cycles. It is easy to observe that every path P satisfies Χi(P) ≤ 3 and that every cycle C satisfies Χi(C) ≤ 4 (the only cycles with incidence chromatic number 3 being the cycles whose length is divisible by 3).

Trees. For every tree T of order at least 2, Χi(T) = Δ(T) + 1 (BM93).

Complete graphs. For every n ≥ 2, Χi(Kn) = n = Δ(Kn) + 1 (BM93).

Complete bipartite graphs. For every mn ≥ 2, Χi(Km,n) = m + 2 = Δ(Km,n) + 2 (BM93).

Complete multipartite graphs. The previous result has been extended to general complete multipartite graphs by Janczewski, Małafiejska and Małafiejski in (JMM18). They proved that the incidence chromatic number of such a graph K is at most Δ(K) + 2, and equals Δ(K) + 1 if and only if the smallest part has only one vertex.

Graph classes

Graphs with maximum degree three

In (SLC02), Shiu, Lam and Chen proved that some subclasses of cubic graphs (e. g. Hamiltonian cubic graphs) have incidence chromatic number at most Δ + 2 and conjectured that this should be true for every cubic graph. Wu proved in (Wu09) that the conjecture holds for cubic graphs having a Hamiltonian path and for bridgeless cubic graphs of (very) high girth (this result was published in 2009 but obtained in 2004).
This conjecture was proven to be true by Maydanskyi (Ma05), who established that every graph with maximum degree at most 3 has incidence chromatic number at most 5. In (LT08), Li and Tu proved that it is NP-complete to determine whether a semi-cubic graph (that is a graph with maximum degree 3, all of whose vertices have degree 1 or 3) has incidence chromatic number 4 or 5.
In (JMM18), Janczewski, Małafiejska and Małafiejski proved that it is NP-complete to determine whether a bipartite semi-cubic graph has incidence chromatic number 4.

Graphs with maximum degree four

In (GLS16a), Gregor, Lužar and Soták proved that every graph with maximum degree four has incidence chromatic number at most 7.
In (FO16), Fahimi and Omoomi provided several sufficient conditions for a graph with maximum degree four to have incidence chromatic number at most 6. However, whether all graphs with maximum degree four satisfy the (Δ + 2)-conjecture or not is still an open question.

Regular graphs

In (Su12), Sun characterized r-regular graphs with incidence chromatic number r + 1, by proving that they are exactly those graphs whose set of vertices is a disjoint union of r + 1 dominating sets. (Recall that a subset S of V(G) is a dominating set if every vertex in V(G) - S has a neighbor in S.)
This result can be made more explicit for cubic graphs as follows. If G is a cubic graph, then Χi(G) = 4 if and only if (1) there exists a dominating set S in G with |S| = |V(G)| / 4, (2) the graph G - S is a disjoint union of cycles of length divisible by 3, and (3) the vertices of every cycle can be labeled abcabc... in such a way that every two vertices in G - S with the same label do not have a common neighbor in S (Su12).

Hypercubes

In (PCYW14), Pai, Chang, Yang and Wu studied the incidence chromatic number of the n-dimensional hypercube Qn and proved the following: (1) if p ≥ 1 and n = 2p - 1, then Χi(Qn) = n + 1 and (2) if p ≥ 2 and n = 2p - 2, or p,q ≥ 1 and n = 2p + 2q - 2, or p,q ≥ 2 and n = 2p + 2q - 3, then Χi(Qn) = n + 2. Moreover, in any other case, Χi(Qn) ≥ n + 2. (In some cases, this value is proved to be at most n + 3.)

k-degenerated graphs

A graph G is said to be k-degenerated if every subgraph of G contains a vertex of degree at most k. Hosseini Dolama, Sopena and Zhu proved in (HSZ04) that every k-degenerated graph admits an incidence (Δ + 2k – 1, k)-coloring and, thus, has incidence chromatic number at most Δ + 2k - 1.
In (HS05), Hosseini Dolama and Sopena proved that every 3-degenerated graph admits an incidence (Δ + 4, 3)-coloring and, thus, has incidence chromatic number at most Δ + 4.

Partial k-trees

A partial k-tree is a subgraph of a k-tree and every k-tree can be obtained from the complete graph Kk by a sequence of vertex insertions, each such new vertex being linked to an existing clique of size k. Therefore, every partial k-tree is clearly k-degenerated and, thus, has incidence chromatic number at most Δ + 2k – 1. Similarly, every partial 3-tree has incidence chromatic number at most Δ + 4.
The class of partial 2-trees corresponds to the class of K4-minor free graphs and strictly contains the class of outerplanar graphs. In (HSZ04), Hosseini Dolama, Sopena and Zhu proved that every partial 2-tree admits an incidence (Δ + 2, 2)-coloring and, thus, has incidence chromatic number at most Δ + 2, and that this bound is tight (consider for instance the cycles of length not divisible by 3).

Outerplanar graphs

Since every outerplanar graph is a partial 2-tree, we get from (HSZ04) that every outerplanar graph admits an incidence (Δ + 2, 2)-coloring and, thus, has incidence chromatic number at most Δ + 2. Moreover, this bound is clearly tight (consider again the cycles of length not divisible by 3).
In (SS08), Shiu and Sun observed that this bound can be decreased to Δ + 1 for outerplanar graphs with girth at least 7, since Wang and Lih proved in (WL03) that the square of every such graph can be properly vertex-colored with at most Δ + 1 colors (which implies that every outerplanar graph with girth at least 7 admits an incidence + 1, 1)-coloring).

Planar graphs

From the result of (HSZ04) on k-degenerated graphs, we get that every planar graph has incidence chromatic number at most Δ + 9, since every planar graph contains a vertex of degree at most 5. In the same paper, Hosseini Dolama, Sopena and Zhu improved this bound and proved that every planar graph admits an incidence (Δ + 7, 7)-coloring and, thus, has incidence chromatic number at most Δ + 7.
In (Wu09) (results obtained in 2004), Wu observed that this bound can be decreased to Δ + 5 for planar graphs with girth at least 7, since Wang and Lih proved in (WL03) that the square of every such graph can be properly vertex-colored with at most Δ + 5 colors (which implies that every planar graph with girth at least 7 admits an incidence (Δ + 5, 1)-coloring). This result has then been improved by Hosseini Dolama and Sopena in (HS05): since every triangle-free planar graph is 3-degenerated (see above), every such graph admits an incidence (Δ + 4, 3)-coloring and, thus, has incidence chromatic number at most Δ + 4. Bonamy, Hocquard, Kerdjoudj and Raspaud (BHKR17) decreased this bound to Δ + 3 for triangle-free planar graphs with maximum degree at least 7.
In (HS05), Hosseini Dolama and Sopena also observed that since every planar graph with girth at least 6 is 2-degenerated, every such graph admits an incidence (Δ + 3, 2)-coloring and, thus, has incidence chromatic number at most Δ + 3. Moreover, they proved that every planar graph with girth at least 6 and maximum degree at least 5 admits an incidence (Δ + 2, 2)-coloring and, thus, has incidence chromatic number at most Δ + 2.
Finally, they proved that every planar graph with girth at least 11 admits an incidence (Δ + 2, 2)-coloring and, thus, has incidence chromatic number at most Δ + 2 and that every planar graph with girth at least 16 and maximum degree at least 4 admits an incidence (Δ + 1, 1)-coloring and, thus, has incidence chromatic number at most Δ + 1. This last result has been improved by Bonamy, Lévęque and Pinlou (BLP14) who decreased the bound of 16 for the girth to 14.
The general upper bound for planar graphs has been improved by Yang in (Ya12, written in 2007) who proved, using the link between the incidence chromatic number, the star arboricity and the chromatic index of a graph (see above), that Χi(G) ≤ Δ + 5 for every planar graph G with Δ ≠ 6 (if Δ = 6, then Χi(G) ≤ 12). The bound of 12 for planar graphs with Δ = 6 was then decreased to 10 by Kardoš, Maceková, Mockovčiaková, Sopena and Soták in (KMMSS18).
In (HKR17), Hocquard, Kerdjoudj and Raspaud considered the case of planar graphs without adjacent small cycles. They proved that Χi(G) ≤ Δ + 4 for every planar graph G without a 3-cycle adjacent to a 4-cycle, and that Χi(G) ≤ Δ + 3 for every planar graph G without 4-cycles and 5-cycles and with Δ ≥ 5 (if Δ = 4, they proved Χi(G) ≤ 8).

Grids

The rectangular grid Gm,n is the Cartesian product of Pm by Pn, the two paths with m and n vertices, respectively. The toroidal grid Tm,n is the Cartesian product of Cm by Cn, the two cycles on m and n vertices, respectively. In (HWC04), Huang, Wang and Chung proved that the incidence chromatic number of every rectangular grid is 5. In (SW13), Sopena and Wu proved that the incidence chromatic number of the toroidal grid Tm,n is 5 if m,n ≡ 0 (mod 5) and 6 otherwise.

Halin graphs

A Halin graph is a planar graph obtained from a tree with no vertex of degree 2 by adding a cycle connecting all its leaves. In (WCP02), Wang, Chen and Pang proved that every Halin graph H with Δ(H) ≥ 5 satisfies Χi(H) = Δ(H) + 1. Li and Liu (LL08) proved that if T denotes the "tree part" of a Halin graph H, then Χi(H2) ≤ Δ(T2) + Δ(T) + 8 (recall that H2 stands for the square of H).
In (SS08), Shiu and Sun proved that every cubic Halin graph H, except K4, has incidence chromatic number Δ(H) + 2 = 5. This result was then extended by Meng, Guo and Su (MGS12) who proved that every pseudo-Halin graph G satisfies the (Δ + 2)-conjecture (a pseudo-Halin graph is a 2-connected planar graph with minimum degree 3 such that deleting the edges of a single face yields a tree; every Halin graph is therefore a pseudo-Halin graph).

Powers of cycles

In (NN12), Nakprasit and Nakprasit considered incidence colorings of powers of cycles (recall that the k-th power Gk of a graph G is the graph obtained from G by adding all edges linking vertices at distance at most k in G). Except for a finite number of cases for each k, they proved that k-th powers of cycles satisfy the (Δ + 2)-conjecture. Moreover, they also prove that, when n is divisible by 2k + 1, Χi(Cnk) = 2k + 1 = Δ(Cnk) + 1.

Product graphs

In (GLS16b), Gregor, Lužar and Soták propose several sufficient conditions on the two factor graphs of a Cartesian product graph G for G having incidence chromatic number at most Δ(G) + 2.
Recall that the direct product G × H of the graphs G and H is the graph with vertex set V(G) × V(H) and such that (g,h)(g′,h′) is an edge if and only if ghE(G) and g′h′E(H). In (Ya12), Yang proved that for every G and H, Χi(G × H) ≤ min { Χi(G)Δ(H), Δ(G)Χi(H) }.

Graphs with bounded maximum average degree

The average degree ad(G) of a graph G is given by ad(G) = 2|E(G)| / |V(G)|. The maximum average degree mad(G) of a graph G is then the maximum value of the average degrees of its subgraphs. A well known fact is that every planar graph G with girth at least g has maximum average degree less than 2g / (g - 2). Therefore, every result for a family of graphs with bounded maximum average degree applies to a family of planar graphs with high girth.
Hosseini Dolama and Sopena proved in (HS05) that every graph with maximum average degree less than 3 (resp. 22/9) and maximum degree Δ has incidence chromatic number at most Δ + 3 (resp. Δ + 2), and that every graph with maximum average degree less than 3 and maximum degree Δ ≥ 5 has incidence chromatic number at most Δ + 2. Bonamy, Lévęque and Pinlou proved in (BLP14) that every graph with maximum average degree less than 7/3 and maximum degree Δ ≥ 4 has incidence chromatic number at most Δ + 1.
A general result was given by Bonamy, Hocquard, Kerdjoudj and Raspaud in (BHKR17). They proved that every graph with maximum average degree less than k and maximum degree Δ ≥ (k2 + 3k)/2 - 2 has incidence chromatic number at most Δ + k - 1. Moreover, they also proved that every graph with maximum average degree less than 4 (resp. 9/2, 5, 5, 6, 6) and maximum degree Δ ≥ 7 (resp. Δ ≥ 9, Δ ≥ 9 or Δ ≤ 5, 6 ≤ Δ ≤ 8, Δ ≥ 12 or Δ ≤ 6, 7 ≤ Δ ≤ 11) has incidence chromatic number at most Δ + 3 (resp. Δ + 4, Δ + 5, Δ + 6, Δ + 6, Δ + 7).
Kardoš, Maceková, Mockovčiaková, Sopena and Soták proved in (KMMSS18) that every graph with maximum average degree less than 3 and maximum degree Δ ≥ 4 has incidence chromatic number at most Δ + 2 (thus improving the previous result from (HS05)), and that every graph with maximum average degree less than 10/3 and maximum degree Δ ≥ 8 has also incidence chromatic number at most Δ + 2.

The incidence coloring game

In (An09), Andres studied the incidence coloring game, which corresponds to the incidence version of the usual coloring game (see (BGKZ07) for a survey on the coloring game). This game is a two-person game played on a graph G with a set C of colors. Two players, Alice and Bob, alternate turns with Alice having the first move. On her/his turn, each player has to assign a color from the set C to some uncolored incidence of G. Alice wins the game if all the incidences of G are eventually colored, otherwise Bob wins the game. The incidence game chromatic number ig(G) of a graph G is then defined as the smallest integer k such that Alice has a winning strategy when playing the incidence coloring game on G with a set C of k colors.
In (An09), Andres proved that if G is a k-degenerated graph with maximum degree Δ(G) then ig(G) ≤ 2Δ(G) + 4k - 2. Moreover, ig(G) ≤ 2Δ(G) + 3k - 1 when Δ(G) ≥ 5k - 1 and ig(G) ≤ Δ(G) + 8k - 2 when Δ(G) ≤ 5k - 1. Since planar graphs, outerplanar graphs and forests are respectively 5-, 2- and 1-degenerate, we get that the incidence game chromatic number of such graphs is at most 2Δ(G) + 18, 2Δ(G) + 6 and 2Δ(G) + 2, respectively.
Recall that the arboricity of a graph G is the minimum number of forests into which its set of edges can be partitioned. In (CS13), Charpentier and Sopena proved that if G has maximum degree Δ(G) and arboricity a(G) then ig(G) ≤ ⌊(3Δ(G) - a(G))/2⌋ + 8a(G) - 2, thus improving the result of Andres since every k-degenerated graph has arboricity at most k. Since the arboricity of planar graphs, outerplanar graphs and forests is at most 3, 2 and 1, respectively, we get that the incidence game chromatic number of such graphs is at most ⌈3Δ(G)/2⌉ + 21, ⌈3Δ(G)/2⌉ + 14 and ⌈3Δ(G)/2⌉ + 6, respectively.
In (An09), Andres also determined the incidence game chromatic number of stars, wheels and cycles. Let Sk (resp. Wk) denote the star (resp. the wheel) whose central vertex has degree k and Ck denote the cycle on k vertices. We then have ig(S2k) = 3k (for k ≥ 1), ig(S2k+1) = 3k + 2 (for k ≥ 0), ig(W2k) = 3k (for k ≥ 7), ig(W2k+1) = 3k + 2 (for k ≥ 6) and ig(Ck) = 5 (for k ≥ 7).
In (Ki11), Kim observed that ig(Ck) = 5 also for every k ≥ 3. He also considered the incidence game chromatic number of paths and proved that ig(Pk) = 5 for every path Pk with k ≥ 13 vertices. He finally observed that any subgraph G of the wheel Wk having the star Sk as a subgraph satisfies ig(G) = ⌈ 3k/2 ⌉ whenever k ≥ 13.

Interval incidence colorings

An incidence coloring of a graph G is an interval incidence coloring if, for every vertex v of G, the set A-(v) is an interval, that is A-(v) = {a,...,a+k} for some positive integers a and k. The interval incidence chromatic number Χii(G) of a graph G is then defined as the smallest number of colors required for an interval incidence coloring of G. Observe that Χi(G) ≤ Χii(G) obviously holds for every graph G.
Interval incidence colorings have been introduced by Janczewski, Małafiejska and Małafiejski in (JMM14a), motivated by the multicasting communication in a multifiber WDM (wavelength-division multiplexing) all-optical star network (BG05). They prove in (JMM14a) that the relation Χii(G) ≤ 2Δ(G) holds for every bipartite graph G and that equality holds for regular bipartite graphs. Moreover, they fully characterize subcubic bipartite graphs that admit an interval incidence coloring using 4, 5 or 6 colors. They also prove that, for bipartite graphs with maximum degree 4, deciding interval incidence 5-colorability can be done in linear time while deciding interval incidence 6-colorability is NP-complete. Finally, they provide an O(nΔ3.5logΔ) time algorithm for optimal interval incidence coloring of trees with maximum degree Δ.
The same authors continue the study of interval incidence colorings in (JMM15), where the following is proved:

• Χii(G) ≤ Δ(G) + 2 if G is a path or a cycle (with Χii(G) = Δ(G) + 1 if and only if G is a path of length at most 4),
• Χii(K1,n) = Δ(K1,n) + 1 for every n ≥ 1,
• Χii(Wn) = Δ(Wn) + 2 + (n mod 2), for every n ≥ 3 (Wn denotes the wheel obtained from the cycle Cn by adding a universal vertex),
• Χii(Kn) = 2Δ(Kn) = 2n - 2,
• Χii(Kn1,...,nk) = 2(n1 + ... + nk) - max { ni + nj, i,j = 1,...,k and i ≠ j },
• for graphs with maximum degree 3, deciding interval incidence 4-colorability can be done in linear time while deciding interval incidence 5-colorability is NP-complete.
• for every k ≥ 5 there is a tree Tk with Δ(Tk) = k such that there exists a subgraph Hk of Tk for which Χii(Hk) > Χii(Tk), thus showing that the property of having interval incidence chromatic number at most k is not hereditary for k ≥ 5.

Moreover, in (MM17), Małafiejska and Małafiejski prove that the inequality Χii(G) ≤ 6 holds for every subcubic graph G with Δ(G) = 3.

Fractional incidence colorings

In (Ya12), Yang introduced and studied the fractional version of incidence colorings, defined as follows. A t-tuple incidence k-coloring of a graph G assigns a set of t colors from the set {1,...,k} to each incidence of G in such a way that adjacent incidences get disjoint sets of colors. (A 1-tuple incidence k-coloring is therefore an incidence k-coloring.) The fractional incidence chromatic number of G is then the infimum of the fractions k/t such that G admits a t-tuple incidence k-coloring.
Yang generalized Guiduli's results on incidence colorings (Gu97) and proved that every graph G with maximum degree Δ has fractional incidence chromatic number at most Δ + 20.log Δ + 84 and that there exist graphs with fractional incidence chromatic number at least Δ(G) + Ω(log Δ(G)).

References

• [BGKZ07] T. Bartnicki, J. Grytczuk, H.A. Kierstead and X. Zhu. The map coloring game. Amer. Math. Monthly 114:793-803 (2007).

• [BHKR17] M. Bonamy, H. Hocquard, S. Kerdjoudj and A. Raspaud. Incidence coloring of graphs with high maximum average degree. Discrete Appl. Math. 227:29-43 (2017). 10.1016/j.dam.2017.04.029

• [BLP14] M. Bonamy, B. Lévęque and A. Pinlou. 2-distance coloring of sparse graphs. J. Graph Theory 77(3):190-218 (2014). doi:10.1002/jgt.21782

• [BG05] R. Brandt and T.F. Gonzalez. Wavelength assignment in multifiber optical star networks under the multicasting communication mode. J. Inter. Net. 6(4):383–405 (2005). doi:10.1142/S0219265905001484

• [CS13] C. Charpentier and E. Sopena. Incidence coloring game and arboricity of graphs. In: International Workshop on Combinatorial Algorithms - IWOCA 2013 (July 10-12, Rouen, France), Lecture Notes in Comput. Sci. 8288:106-114 (2013). link

• [FO16] H. Fahimi and B. Omoomi. On incidence coloring for some graphs of maximum degree 4. Ars Combinatoria 125:33-45 (2016). link

• [GLS16a] P. Gregor, B. Lužar, R. Soták. Note on incidence chromatic number of subquartic graphs. J. Comb. Optim. (2016). doi:0.1007/s10878-016-0072-2.

• [GLS16b] P. Gregor, B. Lužar, R. Soták. On incidence coloring conjecture in Cartesian products of graphs. Discrete Appl. Math. 213:93-100 (2016). doi:10.1016/j.dam.2016.04.030.

• [HH12] S.G. Hartke and G.T. Helleloid. Reconstructing a graph from its arc incidence graph. Graphs Combin. 28(5):637-652 (2012). doi:10.1007/s00373-011-1073-7

• [HKR17] H. Hocquard, S. Kerdjoudj and A. Raspaud. Incidence coloring of planar graphs without adjacent small cycles. J. Combin 8(1):167-187 (2017). doi:10.4310/JOC.2017.v8.n1.a6

• [HS05] M. Hosseini Dolama and É. Sopena. On the maximum average degree and the incidence chromatic number of a graph. Discrete Math. and Theoret. Comput. Sci. 7:203-216 (2005). dm070112.pdf

• [HSZ04] M. Hosseini Dolama, É. Sopena and X. Zhu. Incidence coloring of k-degenerated graphs. Discrete Math. 283(1-3):121-128 (2004). doi:10.1016/j.disc.2004.01.015

• [HWC04]] C.I. Huang, Y.L. Wang and S.S. Chung. The incidence coloring number of meshes. Computers and Math. with Appl. 48:1643-1649 (2004). doi:10.1016/j.camwa.2004.02.006

• [JMM14a] R. Janczewski, A. Małafiejska and M. Małafiejski. Interval incidence coloring of bipartite graphs. Discrete Appl. Math. 166:131-140 (2014). doi:10.1016/j.dam.2013.10.007

• [JMM15] R. Janczewski, A. Małafiejska and M. Małafiejski. Interval incidence coloring. Discrete Appl. Math., 182:73-83 (2015). doi:10.1016/j.dam.2014.03.006

• [JMM18] R. Janczewski, A. Małafiejska and M. Małafiejski. On incidence coloring of complete multipartite and subcubic bipartite graphs. Discuss. Math. Graph Theory, 38:107-119 (2018). doi:10.7151/dmgt.1995

• [KMMSS18] F. Kardoš, M. Maceková, M. Mockovčiaková, É. Sopena and R. Soták. Incidence coloring - Cold cases. Discuss. Math. Graph Theory, accepted (2018). doi:10.7151/dmgt.2140

• [Ki11] J.Y. Kim. The incidence game chromatic number of paths and subgraphs of wheels. Discrete Appl. Math., 159(8):683-694 (2011). doi:10.1016/j.dam.2010.01.001

• [LT08] X. Li and J. Tu. NP-completeness of 4-incidence colorability of semi-cubic graphs. Discrete Math. 308(7):1334-1340 (2008). doi:10.1016/j.disc.2007.03.076

• [MM17] A. Małafiejska and M. Małafiejski. Interval incidence coloring of subcubic graphs. Discuss. Math. Graph Theory 37:427-441 (2017). doi:10.7151/dmgt.1962

• [Ma05] M. Maydanskiy. The incidence coloring conjecture for graphs of maximum degree three. Discrete Math. 292:131-141 (2005). doi:10.1016/j.disc.2005.02.003

• [NN14] K. Nakprasit and K. Nakprasit. The strong chromatic index of graphs and subdivisions. Discrete Math. 317:75-78 (2014). doi:1016/j.disc.2013.11.005

• [PCYW14] K.J. Pai, J.M. Chang, J.S. Yang and R.Y. Wu. Incidence coloring on hypercubes. Theoret. Comput. Sci. 557:59-65 (2014). doi:10.1016/j.tcs.2014.08.017 (The algorithm proposed in this paper was wrong, it has been corrected in (PCYW16).)
• [PCYW16] K.J. Pai, J.M. Chang, J.S. Yang and R.Y. Wu. Corrigendum to "Incidence coloring on hypercubes". Theoret. Comput. Sci. 651:87-88 (2016). doi:10.1016/j.tcs.2016.08.001

• [Su12] P.K. Sun. Incidence coloring of regular graphs and complement graphs. Taiwanese J. Math. 16(6):2289-2295 (2012). Available here

• [WCP02] S.-D. Wang, D.-L. Chen, S.-C. Pang. The incidence coloring number of Halin graphs and outerplanar graphs. Discrete Math. 256(1-2):397-405 (2002). doi:10.1016/S0012-365X(01)00302-8

• [WL03] W.F. Wang and K.W. Lih. Labeling planar graphs with conditions on girth and distance two. SIAM J. Discrete Math. 17(2):264-275 (2003). doi:10.1137/S0895480101390448

• [Ya12] D. Yang. Fractional incidence coloring and star arboricity of graphs. Ars Combin. 105:213-224 (2012), written in 2007.