# 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. *Some arXiv papers, yet unpublished, might also be cited, in which case the corresponding paragraphs appear in italics.*

If you have any suggestion, or new results not reported here, please do not hesitate to contact me at *eric.sopena@labri.fr*.

## Contents

- Definitions and notation (definitions, example, notation, (k,p)-incidence colorings, links with other notions)
- General results (complexity, general lower bound, general upper bounds, Nordhaus-Gaddum-type inequality, the “(Δ + 2)-conjecture", simple graph classes)
- Graph classes (graphs with maximum degree three, graphs with maximum degree four, regular graphs, hypercubes, k-degenerated graphs, partial k-trees, outerplanar graphs, planar graphs, grids, Halin graphs, powers of cycles, product graphs, graphs with bounded maximum average degree)
- Incidence choosability
- The incidence coloring game
- Interval incidence colorings
- Fractional incidence colorings
- Incidence colorings of digraphs
- References

## 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 *C _{4} * 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

*C*using 4 colors is depicted in figure (b). (It can easily be checked that the incidences of

_{4}*C*cannot be colored by using only 3 colors.)

_{4}### 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.

### Links with other notions

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*) / *v* ∈ *V*(*G*), *e* ∈ *E*(*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,v* ∈ *V*(*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 *G*^{2} of *G*. Conversely, from every proper *k*-vertex-coloring of *G*^{2}, 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*) =

*Χ*(

*G*) and

^{2}*Χ*(

_{i}*G*) ≤

*Χ*(

*G*) for every graph

^{2}*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 ≤

*i*≤

*st*(

*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)).

### Nordhaus-Gaddum-type inequality

In (Su12), Sun established the following Nordhaus-Gaddum-type inequality: for every graph *G* with *n* vertices, *G* ≠ *K _{n}*,

*G*≠

^{c}*K*,

_{n}*n*+ 2 ≤

*Χ*(

_{i}*G*) +

*Χ*(

_{i}*G*) ≤ 2

^{c}*n*- 1, where

*G*stands for the complement of

^{c}*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}*(

*K*) =

_{n}*n*=

*Δ*(

*K*) + 1 (BM93).

_{n}**Complete bipartite graphs.** For every *m* ≥ *n* ≥ 2, *Χ _{i}*(

*K*) =

_{m,n}*m*+ 2 =

*Δ*(

*K*) + 2 (BM93).

_{m,n}**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 *Q _{n}* and proved the following: (1) if

*p*≥ 1 and

*n*= 2

^{p}- 1, then

*Χ*(

_{i}*Q*) =

_{n}*n*+ 1 and (2) if

*p*≥ 2 and

*n*= 2

^{p}- 2, or

*p,q*≥ 1 and

*n*= 2

^{p}+ 2

^{q}- 2, or

*p,q*≥ 2 and

*n*= 2

^{p}+ 2

^{q}- 3, then

*Χ*(

_{i}*Q*) =

_{n}*n*+ 2. Moreover, in any other case,

*Χ*(

_{i}*Q*) ≥

_{n}*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 (*Δ* + 2*k* – 1, *k*)-coloring and, thus, has incidence chromatic number at most *Δ* + 2*k* - 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 *K _{k}* 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

*Δ*+ 2

*k*– 1. Similarly, every partial 3-tree has incidence chromatic number at most

*Δ*+ 4.

The class of partial 2-trees corresponds to the class of

*K*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 (

_{4}-minor free*Δ*+ 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* *G _{m,n}* is the Cartesian product of

*P*by

_{m}*P*, the two paths with

_{n}*m*and

*n*vertices, respectively. The

*toroidal grid*

*T*is the Cartesian product of

_{m,n}*C*by

_{m}*C*, the two cycles on

_{n}*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

*T*is 5 if

_{m,n}*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}*H*) ≤

^{2}*Δ*(

*T*) +

^{2}*Δ*(

*T*) + 8 (recall that

*H*stands for the square of

^{2}*H*).

In (SS08), Shiu and Sun proved that every cubic Halin graph

*H*, except

*K*has incidence chromatic number

_{4},*Δ*(

*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 *G ^{k}* 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 2

*k*+ 1,

*Χ*(

_{i}*C*) = 2

_{n}^{k}*k*+ 1 =

*Δ*(

*C*) + 1.

_{n}^{k}### 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 *gh* ∈ *E*(*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 2*g* / (*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 *Δ* ≥ (*k*^{2} + 3*k*)/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.

## Incidence choosability

The list version of incidence coloring has been introduced by Benmedjdoub, Bouchemakh and Sopena in (BBS19). Let *L* be a list assignment of the incidences of *G*, that is, a mapping that assigns to every incidence (*v,e*) of *G* a finite list *L*(*v,e*) of colors. The graph *G* is *L*-list incidence colorable if there exists an incidence coloring *f* of *G* satisfying *f*(*v,e*) ∈ *L*(*v,e*) for every incidence (*v,e*) of *G*. The graph *G* is *k-list incidence colorable*, or *k-incidence-choosable*, if, for every list assignment *L* with |*L*(*v,e*)| = *k* for every incidence (*v,e*), *G* is *L*-list incidence colorable. The incidence choice number *ch _{i}*(

*G*) of

*G*is then defined as the smallest integer

*k*such that

*G*is

*k*-incidence-choosable. In this paper, upper bounds on the incidence choice number of several graph classes are established:

- If Δ(
*G*) ≥ 2, then Δ(*G*) ≤ χ_{i}(*G*) ≤*ch*(_{i}*G*) ≤ 3Δ(*G*) - 2. - For every integer
*n*≥ 3,*ch*(_{i}*C*) = 3 if_{i}*n*≡ 0 (mod 3), and*ch*(_{i}*C*) = 4 otherwise._{i} - If
*G*is*d*-degenerate, then*ch*(_{i}*G*) ≤ Δ(*G*) + 2*d*- 1. (This implies in particular*ch*(_{i}*G*) = Δ(*G*) + 1 if*G*is a tree,*ch*(_{i}*G*) = Δ(*G*) + 3 if*G*is*K*-minor free, and_{4}*ch*(_{i}*G*) = Δ(*G*) + 9 if*G*is planar.) - Let
*G*be the square grid with_{m,n}*m*rows and*n*columns,*m*≥*n*. We then have*ch*(_{i}*G*) ≤ 5 if_{m,n}*n*= 2, and*ch*(_{i}*G*) ≤ 6 otherwise._{m,n} - If
*G*is a Halin graph, then*ch*(_{i}*G*) ≤ 6 if Δ(*G*) = 3,4 and*G*≠*W*(the wheel graph with five vertices),_{5}*ch*(_{i}*G*) ≤ 7 if Δ(*G*) = 5 and*G*=*W*, and_{4}*ch*(_{i}*G*) = Δ(*G*) + 1 otherwise. - If
*G*is a hamiltonian cubic graph, then*ch*(_{i}*G*) ≤ 6. - Upper bounds on the incidence choice number of cactuses are also proposed (see (BBS19) for details).

In the same paper, the authors pose the question of determining the incidence choice number of cubic graphs. This question has been answered by Kang and Park in (KP19), who proved that *ch _{i}*(

*G*) ≤ 6 for every loopless cubic multigraph

*G*. A shorter proof of this result has been given by Valicov (

*This result has not been published yet, but is available on arXiv: (2, 3)-bipartite graphs are strongly 6-edge-choosable.*).

## 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* *i _{g}*(

*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

*i*(

_{g}*G*) ≤ 2

*Δ*(

*G*) + 4

*k*- 2. Moreover,

*i*(

_{g}*G*) ≤ 2

*Δ*(

*G*) + 3

*k*- 1 when

*Δ*(

*G*) ≥ 5

*k*- 1 and

*i*(

_{g}*G*) ≤

*Δ*(

*G*) + 8

*k*- 2 when

*Δ*(

*G*) ≤ 5

*k*- 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

*i*(

_{g}*G*) ≤ ⌊(3

*Δ*(

*G*) -

*a*(

*G*))/2⌋ + 8

*a*(

*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

*S*(resp.

_{k}*W*) denote the star (resp. the wheel) whose central vertex has degree

_{k}*k*and

*C*denote the cycle on

_{k}*k*vertices. We then have

*i*(

_{g}*S*) = 3

_{2k}*k*(for

*k*≥ 1),

*i*(

_{g}*S*) = 3

_{2k+1}*k*+ 2 (for

*k*≥ 0),

*i*(

_{g}*W*) = 3

_{2k}*k*(for

*k*≥ 7),

*i*(

_{g}*W*) = 3

_{2k+1}*k*+ 2 (for

*k*≥ 6) and

*i*(

_{g}*C*) = 5 (for

_{k}*k*≥ 7).

In (Ki11), Kim observed that

*i*(

_{g}*C*) = 5 also for every

_{k}*k*≥ 3. He also considered the incidence game chromatic number of paths and proved that

*i*(

_{g}*P*) = 5 for every path

_{k}*P*with

_{k}*k*≥ 13 vertices. He finally observed that any subgraph

*G*of the wheel

*W*having the star

_{k}*S*as a subgraph satisfies

_{k}*i*(

_{g}*G*) = ⌈ 3

*k*/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.5}logΔ) 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}*K*) = Δ(_{1,n}*K*) + 1 for every_{1,n}*n*≥ 1,*Χ*(_{ii}*W*) = Δ(_{n}*W*) + 2 + (_{n}*n*mod 2), for every*n*≥ 3 (*W*denotes the wheel obtained from the cycle_{n}*C*by adding a universal vertex),_{n}*Χ*(_{ii}*K*) = 2Δ(_{n}*K*) = 2_{n}*n*- 2,*Χ*(_{ii}*K*) = 2(_{n1,...,nk}*n*+ ... +_{1}*n*) - max {_{k}*n*+_{i}*n*,_{j}*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*T*with Δ(_{k}*T*) =_{k}*k*such that there exists a subgraph*H*of_{k}*T*for which_{k}*Χ*(_{ii}*H*) >_{k}*Χ*(_{ii}*T*), thus showing that the property of having interval incidence chromatic number at most_{k}*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*)).

## Incidence colorings of digraphs

The study of incidence colorings of digraphs has been initiated by Duffy, MacGillivray, Ochem and Raspaud in (DMGOR19). Let *D* be a digraph. The set *I*(*D*) of incidences of *D* is defined as in the undirected case, each arc *uv* giving two incidences, namely (*u,uv*) and (*v,uv*).
For every arc *uv*, the incidences (*u,uv*) and (*v,uv*) are adjacent and, for every two consecutive arcs *uv* and *vw*, the incidences (*v,uv*) and (*v,vw*) are adjacent, as well as the incidences (*u,uv*) and (*v,vw*), and (*v,uv*) and (*w,vw*). An incidence coloring of *D* is then a mapping that assigns distinct colors adjacent incidences of *D*, and the *oriented incidence chromatic number* χ(*D*) of *D* is the smallest number of colors required for an incidence coloring of *D*.

The authors observed that for every oriented graph *O* (that is, a digraph with no opposite arcs), the inequality χ_{i}(*O*) ≤ χ_{o}(*O*) holds, where χ_{o}(*O*) denotes the oriented chromatic number of *O* (see The Oriented Coloring Page of my website). The authors mainly considered the case of complete symmetric digraphs, and proposed lower and upper bounds on the oriented incidence chromatic number of such digraphs.

## References

- [AA89] I. Algor and N. Alon. The star arboricity of graphs.
*Discrete Math.*75:11-22 (1989). doi:10.1016/0012-365X(89)90073-3

- [An09] S.D. Andres. The incidence game chromatic number.
*Discrete Appl. Math.*157:1980-1987 (2009). doi:10.1016/j.dam.2007.10.021 (see also Erratum to this paper,*Discrete Appl. Math.*158(6):728 (2009). doi:0.1016/j.dam.2009.11.017.)

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

- [BBS19] B. Benmedjdoub, I. Bouchemakh and É. Sopena. Incidence choosability of graphs.
*Discrete Appl. Math.*265:40–55 (2019). doi:10.1016/j.dam.2019.04.027

- [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

- [BM93] R.A. Brualdi and J.J.Q. Massey. Incidence and strong edge colorings of graphs.
*Discrete Math.*122:51-58 (1993). doi:10.1016/0012-365X(93)90286-3

- [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

- [DMGOR19] C. Duffy, G. MacGillivray, P. Ochem and A. Raspaud. Oriented incidence colourings of digraphs.
*Discuss. Math. Graph Theory*39:191-210 (2019). doi:10.7151/dmgt.2076

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

- [Gu97] B. Guiduli. On incidence coloring and star arboricity of graphs.
*Discrete Math.*163:275-278 (1997). doi:10.1016/0012-365X(95)00342-T

- [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

- [KP19] S. Kang and B. Park. On incidence choosability of cubic graphs.
*Discrete Math.*342:1828–1837 (2019). doi:10.1016/j.disc.2019.03.004

- [KMMSS18] F. Kardoš, M. Maceková, M. Mockovčiaková, É. Sopena and R. Soták. Incidence coloring - Cold cases.
*Discuss. Math. Graph Theory*, in press (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

- [LL08] D. Li and M. Liu. Incidence coloring of the squares of some graphs.
*Discrete Math.*308(24):6569-6574 (2008). doi:10.1016/j.disc.2007.11.047

- [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

- [MGS12] X. Meng, J. Guo and B. Su. Incidence coloring of pseudo-Halin graphs.
*Discrete Math.*312:3276-3282 (2012). doi:10.1016/j.disc.2012.07.024

- [NN12] K. Nakprasit and K. Nakprasit. Incidence colorings of the powers of cycles.
*Int. J. Pure and Applied Math.*76(1):143-148 (2012). Available at http://ijpam.eu/contents/2012-76-1/13/13.pdf.

- [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

- [SLC02] W.C. Shiu, P.C.P. Lam and D.-L. Chen. On incidence coloring for some cubic graphs.
*Discrete Math.*252:259-266 (2002). doi:10.1016/S0012-365X(01)00457-5

- [SS08] W.C. Shiu and P.K. Sun. Invalid proofs on incidence coloring.
*Discrete Math.*308(24):6575-6580 (2008). doi:10.1016/j.disc.2007.11.030

- [SW13] É. Sopena and J. Wu. The incidence chromatic number of toroidal grids.
*Discuss. Math. Graph Theory*33:315-327 (2013). doi:dx.doi.org/10.7151/dmgt.1663

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

- [Wu09] J. Wu. Some results on the incidence coloring number of a graph.
*Discrete Math.*309:3866-3870 (2009). doi:10.1016/j.disc.2008.10.027

- [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.