# Incidence coloring of graphs with high maximum average degree 111Work
partially supported by the ANR Grant EGOS (2012-2015) 12 JS02 002 01.

Marthe Bonamy  Hervé Hocquard  Samia Kerdjoudj  André Raspaud  Université
Montpellier 2 - LIRMM 161 rue Ada 34095 Montpellier, France  LaBRI (Université
de Bordeaux), 351 cours de la Libération, 33405 Talence Cedex, France
LIFORCE, Faculty of Mathematics, USTHB, BP 32 El-Alia, Bab-Ezzouar 16111,
Algiers, Algeria

###### Abstract

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$ assigns a color to each
incidence of $G$ in such a way that adjacent incidences get distinct colors.
In 2005, Hosseini Dolama _et al._ [6] proved that every graph with maximum
average degree strictly less than $3$ can be incidence colored with $\Delta+3$
colors. Recently, Bonamy _et al._ [2] proved that every graph with maximum
degree at least $4$ and with maximum average degree strictly less than
$\frac{7}{3}$ admits an incidence $(\Delta+1)$-coloring. In this paper we give
bounds for the number of colors needed to color graphs having maximum average
degrees bounded by different values between $4$ and $6$. In particular we
prove that every graph with maximum degree at least $7$ and with maximum
average degree less than $4$ admits an incidence $(\Delta+3)$-coloring. This
result implies that every triangle-free planar graph with maximum degree at
least $7$ is incidence $(\Delta+3)$-colorable. We also prove that every graph
with maximum average degree less than 6 admits an incidence
$(\Delta+7)$-coloring. More generally, we prove that $\Delta+k-1$ colors are
enough when the maximum average degree is less than $k$ and the maximum degree
is sufficiently large.

###### keywords:

Graph coloring - Incidence coloring - Maximum average degree - Incidence
chromatic number

##  1 Introduction

In the following we only consider simple, non-empty connected graphs. In a
graph $G=(V,E)$, an _incidence_ is an edge $e$ coupled with one of its two
extremities, denoted by $(u,uv)$ or $(v,uv)$. In other words, incidences of
$G$ are in natural bijection with edges in the graph $G_{s}$ obtained from $G$
by subdividing every edge once.

The set of all incidences in $G$ is denoted by $I(G)$, where

$I(G)=\\{(v,e)\in V(G)\times E(G):\mbox{edge $e$ is incident to $v$}\\}$.

Two incidences $(u,e)$ and $(v,f)$ are adjacent if one of the following holds
:

$i)$ $u=v$, $ii)$ $e=f$ and $iii)$ the edge $uv=e$ or $uv=f$.

A _strong incidence of_ a vertex $u$ is an incidence $(u,uv)$ for some $v$. A
_weak incidence of_ a vertex $u$ is an incidence $(v,uv)$ for some $v$. In
both cases, a strong or weak incidence of $u$ can be referred to as an
_incidence of_ $u$.

A proper _incidence coloring_ of $G$ is a coloring of the incidences in such a
way that for every vertex $u$, a strong incidence of $u$ does not receive the
same color as any other incidence of $u$.

This corresponds to an edge coloring of $G_{s}$ such that two incident edges
receive different colors, and no edge is incident with two edges of the same
color. We say that $G$ is _incidence $k$-colorable_ if it can be properly
incidence colored using only integers between $1$ and $k$. Note that this
definition allows for a non-integer value of $k$, though $\lfloor k\rfloor$
could be equivalently considered. We denote by $\chi_{i}(G)$ the incidence
chromatic number of $G$, which is the smallest integer $k$ such that $G$ is
incidence $k$-colorable. The notion of incidence coloring was first introduced
by Brualdi and Massey [3]. And they posed the Incidence Coloring Conjecture,
which states that:

######  Conjecture 1 (Brualdi and Massey [3])

For every graph $G$, $\chi_{i}(G)\leq\Delta(G)+2$.

When Brualdi and Massey defined this variant of coloring, they also provided
tight bounds for its corresponding chromatic number, as follows.

######  Theorem 1 (Brualdi and Massey [3])

For every graph $G$, $\Delta(G)+1\leq\chi_{i}(G)\leq 2\Delta(G)$.

However, in 1997, by observing that the concept of incidence coloring is a
particular case of directed star arboricity introduced by Algor and Alon [1],
Guiduli [4] disproved the Incidence Coloring Conjecture showing that Paley
graphs have an incidence chromatic number at least
$\Delta+\Omega(\log\Delta)$. He also improved the upper bound proposed by
Brualdy and Massey in Theorem 1.

######  Theorem 2 (Guiduli [4])

For every graph $G$, $\chi_{i}(G)\leq\Delta(G)+o(\log\Delta(G))$.

For technical purpose, we use the stronger notion of incidence coloring
introduced by Hosseini Dolama, Sopena and Zhu in 2004 [5], defined as follows.
An incidence $(k,\ell)$-coloring of $G$ is an incidence $k$-coloring such that
for every vertex $u$, at most $\ell$ different colors can appear on weak
incidences of $u$. In particular, one can note that an incidence
$(k,1)$-coloring of a graph is actually tantamount to a square coloring of it,
that is, a proper coloring of its vertices with the additionnal property that
no vertex can have two neighbors with the same color. Indeed, we can consider
the unique color used on the weak incidences of a vertex to be assigned to
that vertex, and conversely. Note again that the notion of incidence
$(k,\ell)$-coloring holds for non-integer values of $k$ and $\ell$.

Let ${\rm mad}(G)=\max\left\\{\frac{2|E(H)|}{|V(H)|},\;H\subseteq G\right\\}$
be the maximum average degree of the graph $G$, where $V(H)$ and $E(H)$ are
the sets of vertices and edges of $H$, respectively. This is a conventional
measure of sparsness of arbitrarily graphs (not necessary planar). For more
details on this invariant see [7] where properties of the maximum degree are
exhibited and where it is proved that maximum average degree may be computed
by a polynomial algorithm. Results linking maximum average degree and
incidence coloring date back to 2005, where Hosseini Dolama and Sopena [6]
started looking for such relationships in the case of graphs with low maximum
average degree (_i.e._ not only bounded, but bounded by a small constant).
However, earlier theorems have implications on graphs with bounded maximum
average degree (_i.e._ bounded by any constant).

###### Theorem 3

[5] Let $k\in\mathbb{N}$, and $G$ be a $k$-degenerate graph. Then $G$ is
incidence $(\Delta(G)+2k-1,k)$-colorable.

As a corollary, it holds immediately that for every integer $k$, a graph $G$
with ${\rm mad}(G)<k$, being $(k-1)$-degenerate, is
$(\Delta(G)+2k-3,k-1)$-colorable. By allowing a lower bound on the maximum
degree $\Delta(G)$, we seek to reduce the number of colors necessary for an
incidence coloring and we prove the following result.

###### Theorem 4

Let $k\in\mathbb{N}$, and $G$ be a graph with maximum degree $\Delta(G)$ and
maximum average degree ${\rm mad}(G)<k$.

  1. 1.

If $\Delta(G)\geq\frac{k^{2}}{2}+\frac{3k}{2}-2$, then $G$ is incidence
$(\Delta(G)+k-1,k-1)$-colorable.

  2. 2.

For all $\alpha>0$, if $\Delta(G)\geq\frac{3\alpha+1}{2\alpha}k-2$, then $G$
is incidence $(\Delta(G)+(1+\alpha)k-1,(1+\alpha)k-1)$-colorable.

When considering small values of $k$, Theorem 4.1 cannot compete with specific
results.

Let us now discuss some such specific cases. The following results were proved
for small values of maximum average degree.

###### Theorem 5

  1. 1.

If $G$ is a graph with $\rm{mad}(G)<3$, then $\chi_{i}(G)\leq\Delta(G)+3$. [6]

  2. 2.

If $G$ is a graph with $\rm{mad}(G)<3$ and $\Delta(G)\geq 5$, then
$\chi_{i}(G)\leq\Delta(G)+2$. [6]

  3. 3.

If $G$ is a graph with $\rm{mad}(G)<\frac{22}{9}$, then
$\chi_{i}(G)\leq\Delta(G)+2$. [6]

  4. 4.

If $G$ is a graph with $\Delta(G)\geq 4$ and $\rm{mad}(G)<\frac{7}{3}$, then
$\chi_{i}(G)=\Delta(G)+1$. [2]

Let us recall results concerning the incidence chromatic number of
$3$-degenerate graphs.

######  Theorem 6 (Hosseini Dolama and Sopena [6])

Every $3$-degenerate graph $G$ admits an incidence $(\Delta(G)+4,3)$-coloring.
Therefore, $\chi_{i}(G)\leq\Delta(G)+4$.

Since a graph $G$ with $\rm{mad}(G)<4$ is $3$-degenerate, the following
corollary can easily be derived from Theorem 6:

###### Corollary 1

If $G$ is a graph with $\rm{mad}(G)<4$, then $G$ admits an incidence
$(\Delta(G)+4,3)$-coloring.

In this paper we improve the previous result by showing the following results
for low maximum average degree.

###### Theorem 7

Let $G$ be a graph with

  1. 1.

$\rm{mad}(G)<4$, then $\chi_{i}(G)\leq\Delta(G)+3$ for every $\Delta(G)\geq 7$
.

  2. 2.

$\rm{mad}(G)<\frac{9}{2}$, then $\chi_{i}(G)\leq\Delta(G)+4$ for every
$\Delta(G)\geq 9$.

  3. 3.

$\rm{mad}(G)<5$, then $\chi_{i}(G)\leq\Delta(G)+5$ for every $\Delta(G)\geq 9$
or $\Delta(G)\leq 5$.

  4. 4.

$\rm{mad}(G)<5$, then $\chi_{i}(G)\leq\Delta(G)+6$ for every
$6\leq\Delta(G)\leq 8$.

  5. 5.

$\rm{mad}(G)<6$, then $\chi_{i}(G)\leq\Delta(G)+6$ for every $\Delta(G)\geq
12$ or $\Delta(G)\leq 6$.

  6. 6.

$\rm{mad}(G)<6$, then $\chi_{i}(G)\leq\Delta(G)+7$ for every
$7\leq\Delta(G)\leq 11$.

For planar graphs, Hosseini Dolama _et al._ [5] proved in 2004 the following
result:

######  Theorem 8 (Hosseini Dolama and Sopena [5])

Every planar graph $G$ admits an incidence $(\Delta+7)$-coloring.

By using the link between the incidence chromatic number, the star arboricity
and the chromatic index of a graph, Yang proved the following theorem:

######  Theorem 9 (Yang [9])

For every planar graph $G$, $\chi_{i}(G)\leq\Delta(G)+5$, if $\Delta(G)\neq 6$
and $\chi_{i}(G)\leq 12$, if $\Delta(G)=6$.

As every planar graph with girth $g$ satisfies $\rm{mad}(G)<\frac{2g}{g-2}$,
the following two corollaries can be derived from Theorem 7.1 and Theorem 7.2.
Along the way, we improve the bound given in Theorem 9 for triangle-free
planar graphs:

###### Corollary 2

Let $G$ be a triangle-free planar graph with $\Delta(G)\geq 7$. Then,
$\chi_{i}(G)\leq\Delta(G)+3$.

###### Corollary 3

Let $G$ be a planar graph with with girth $g\geq 5$ and $\Delta(G)\geq 9$.
Then, $\chi_{i}(G)\leq\Delta(G)+4$.

Moreover if $G$ is a planar graph, then $\rm{mad}(G)<6$. We deduce another
proof of Theorem 8.

###### Corollary 4

Let $G$ be a planar graph. Then, $\chi_{i}(G)\leq\Delta(G)+7$.

We have also a better bound for large maximum degree.

###### Corollary 5

Let $G$ be a planar graph with $\Delta(G)\geq 12$. Then,
$\chi_{i}(G)\leq\Delta(G)+6$.

However, Theorem 4 can be proved with a relatively simple discharging
argument, and gives hope that further development of more complicated
reducible configurations and discharging rules might unlock generic results
with consequences beyond purely extremal.

Before proving our results we introduce some notation.

#### Notation

Let $G$ be a graph. Let $d(v)$ denote the degree of a vertex $v$ in $G$. A
vertex of degree $k$ is called a $k$-vertex. A $k^{+}$-vertex (respectively,
$k^{-}$-vertex) is a vertex of degree at least $k$ (respectively, at most
$k$). A $(l_{1},\cdots,l_{k})$-vertex is a $k$-vertex having $k$-neighbors
$x_{1},\cdots,x_{k}$ such that $d(x_{i})=l_{i}$ for $i\in\\{1,\cdots,k\\}$. We
will also use for $l_{i}$ the notation $l_{i}^{+}$ (respectively $l_{i}^{-}$),
if $x_{i}$ is a vertex of degree at least $l_{i}$ (respectively at most
$l_{i}$).

##  2 Proof of Theorem 4

###  2.1 Structural property

Let $d\in\mathbb{N}$, $k\in\mathbb{N}$ and $\alpha\in\mathbb{R}^{+}$. We
consider $\mathcal{G}_{d}$ the class of graphs with maximum degree at most
$d$, and $\mathcal{H}_{d,\alpha}\subseteq\mathcal{G}_{d}$ the subset of graphs
which are not incidence $(d+(1+\alpha)k-1,(1+\alpha)k-1)$-colorable.

###### Lemma 1

If $G$ is a minimal graph in $\mathcal{H}_{d,\alpha}$, then every $u\in V(G)$
with $d(u)\leq k-1$ has more than $(1+\alpha)k-d(u)$ neighbors of degree at
least $d-k+2$.

Proof
Let $G$ be a minimal counter-example to Theorem 4, and $u\in V(G)$ a witness
of it. Let $p=d(u)$, and $v_{1},\ldots,v_{p}$ be the $p$ neighbors of $u$,
sorted by decreasing degree. By assumption, for every $p\geq i>(1+\alpha)k-p$,
we have $d(v_{i})\leq d-k+1$. By minimality of the counter-example, the graph
$G^{\prime}=G\setminus\\{u\\}$ admits an incidence
$(d+(1+\alpha)k-1,(1+\alpha)k-1)$-coloring. Let us prove that we can extend
the coloring to $G$.

For every $1\leq i\leq p$, we set $e_{i}=(u,uv_{i})$. For every $1\leq
i\leq(1+\alpha)k-p$, we set $f_{i}=(v_{i},uv_{i})$. For every $p\geq
i>(1+\alpha)k-p$, we set $g_{i}=(v_{i},uv_{i})$. When referring to _the
$f_{i}$’s_, we actually refer to the set $\\{f_{i}|1\leq
i\leq(1+\alpha)k-p\\}$. Note that $(1+\alpha)k-p\geq 1$. We can similarly
define _the $e_{i}$’s_ and _the $g_{i}$’s_.

Let us now evaluate how many free colors are available, in the worst case, to
color each incidence of $u$. Let $1\leq i\leq p$, and consider $e_{i}$. We
have to ensure that at most $(1+\alpha)k-1$ different colors appear on weak
incidences of $v_{i}$. Let $S_{i}$ be the set of colors appearing on strong
incidences of $v_{i}$. We have $|S_{i}|=d(v_{i})-1\leq d-1$. Since there are
$d+(1+\alpha)k-1$ different colors, and by assumption, there is a set $W_{i}$
of $(1+\alpha)k-1$ different colors, with $W_{i}\cap S_{i}=\emptyset$, from
which the weak incidences of $v_{i}$ are colored. Then, $e_{i}$ might be
colored with any element of $W_{i}$, which makes $(1+\alpha)k-1$ colors
available for $e_{i}$. If $i\leq(1+\alpha)k-p$, we consider $f_{i}$. From the
initial $d+(1+\alpha)k-1$ colors, we remove $W_{i}$ ($(1+\alpha)k-1$ colors)
for the weak incidences of $v_{i}$, and at most $d(v_{i})-1\leq d-1$ for the
strong incidences of $v_{i}$. Therefore, $f_{i}$ has at least one available
color, which by construction does not belong to $W_{i}$. If $i>(1+\alpha)k-p$,
we consider $g_{i}$. From the initial $d+(1+\alpha)k-1$ colors, we remove
$W_{i}$ ($(1+\alpha)k-1$ colors) for the weak incidences of $v_{i}$, and
$d(v_{i})-1\leq d-k$ for the strong incidences of $v_{i}$. Therefore, $g_{i}$
has at least $k$ available colors.

We extend the coloring to $G$ by coloring the $f_{i}$’s, the $e_{i}$’s and the
$g_{i}$’s, in that order. Let us now argue why this is possible. Since all
$v_{i}$’s are distinct vertices, no two $(v_{i},uv_{i})$’s can be adjacent.

Therefore, we first color independently each $f_{i}$ with a color that does
not belong to $W_{i}$.

Now, for every $i>(1+\alpha)k-p$, $e_{i}$ has at least
$(1+\alpha)k-1-((1+\alpha)k-p)=p-1$ colors available. For every
$i\leq(1+\alpha)k-p$, the same analysis goes except that $f_{i}$ was colored
with a color that was not available for $e_{i}$, which allows for one more
color: $e_{i}$ has at least $(1+\alpha)k-1-((1+\alpha)k-p-1)=p$ colors
available. Consequently, we can color the $e_{i}$’s by decreasing index.

Now, each $g_{i}$ has at least $k-p\geq 1$ colors available, and we color the
$g_{i}$’s independently. Since $p=d(u)\leq k-1\leq(1+\alpha)k-1$, the coloring
obtained for $G$ is an incidence $(d+(1+\alpha)k,(1+\alpha)k)$-coloring.
$\Box$

Note that Lemma 1 implies that $G$ contains no vertex with degree at most
$\frac{(1+\alpha)k}{2}$.

###  2.2 Discharging procedure

Let us try to find sufficient conditions on $d$ that ensure all minimal graphs
in $\mathcal{H}_{d,\alpha}$ have average degree at least $k$. Let $G$ be a
minimal graph in $\mathcal{H}_{d,\alpha}$.

For this purpose, we use a discharging procedure. We assign a weight
$\omega(u)=d(u)-k$ to every vertex $u$ of $G$. If we can redistribute the
weight in such a way that every vertex has a non-negative weight, then
$ad(G)\geq k$. Note that at the beginning, only vertices of degree $k-1$ or
less have negative weight. A naive discharging rule to correct this is as
follows:

Let $M,c\in\mathbb{R}$.

  * 1.

R: Every vertex of degree at least $M$ gives a weight of $c$ to every incident
vertex of degree at most $(k-1)$.

We try to find good values of $M$ and $c$ so that no vertex has a negative
weight after the discharging procedure. For $R$ to be well-defined and for us
to be able to apply Lemma 1 in order to ensure that every vertex of degree at
most $k-1$ has enough neighbors of degree at least $M$, we need (1).

$k\leq M\leq d-k+2$ (1)

For every vertex of degree at least $M$ to have a non-negative weight after
application of $R$, it is sufficient to satisfy $M-k-c\times M\geq 0$, thus
(2), in case all neighbors are of degree less than $k$ and need to receive
$c$.

$M\geq\frac{k}{1-c}$ (2)

We assume from now on that (1) and (2) are satisfied. Every vertex of degree
less than $M$ and at least $k$ is not affected by $R$ and has a constant non-
negative weight. Therefore, we only need to look at sufficient conditions for
vertices of degree at most $k-1$ to have a non-negative weight. Note that
Lemma 1 implies that $G$ contains no vertex with degree
$\frac{(1+\alpha)k}{2}$ or less. Because $k$ is always an integer while
$(1+\alpha)k$ may not always be, we distinguish the case $\alpha=0$ from the
rest. Let $u$ be a vertex of degree $p$ at most $k-1$.

  1. 1.

Assume $\alpha=0$. By Lemma 1, $u$ has more than $k-p$ (thus at least $k-p+1$)
neighbors of degree at least $d-k+2\geq M$. Hence $u$ receives at least
$(k-p+1)\times c$. For $u$ to have a non-negative final weight, it suffices to
have $p-k+c\times(k-p+1)\geq 0$, thus (3).

$c\geq 1-\frac{1}{k+1-p}$ (3)

The strongest constraint comes from smallest possible $p$, _i.e._
$\frac{k+1}{2}$ (if $k$ is odd, otherwise $p$ has to be at least
$\frac{k}{2}+1>\frac{k+1}{2}$). Therefore, we can replace (3) with (4).

$c\geq 1-\frac{2}{k+1}$ (4)

We know that if $d$, $M$ and $c$ satisfy (1), (2) and (4), then
$\rm{ad}(G)\geq k$ (where $\rm{ad}(G)$ denotes the average degree of $G$). We
can take $c=1-\frac{2}{k+1}$, $M=\frac{k(k+1)}{2}$. It follows that any
$d\geq\frac{k(k+3)}{2}-2$ guarantees the conclusion.

  2. 2.

Case $\alpha>0$. By Lemma 1, $u$ has more than $(1+\alpha)k-p$ neighbors of
degree at least $d-k+2\geq M$. Hence $u$ receives at least
$((1+\alpha)k-p)\times c$. For $u$ to have a non-negative final weight, it
suffices to have $p-k+c\times((1+\alpha)k-p)\geq 0$, or equivalently $c\geq
1-\frac{\alpha k}{(1+\alpha)k-p}$. The constraint is strongest when $p$ is
smallest possible, _i.e._ $\frac{(1+\alpha)k}{2}$, hence (5).

$c\geq 1-\frac{2\alpha k}{(1+\alpha)k}=1-\frac{2\alpha}{1+\alpha}$ (5)

We know that if $d$, $M$ and $c$ satisfy (1), (2) and (5), then
$\rm{ad}(G)\geq k$. We can take $c=1-\frac{2\alpha}{1+\alpha}$,
$M=\frac{(\alpha+1)k}{2\alpha}$. It follows that any
$d\geq\frac{k(3\alpha+1)}{2\alpha}-2$ guarantees the conclusion.

$\square$

Before proving Theorem 7, we have to introduce some notations used by Hosseini
Dolama _et al._ [5].

######  Definition 1 (Hosseini Dolama _et al._ [5])

Let $G$ be a graph. A partial incidence coloring $\phi^{\prime}$ of $G$, is an
incidence coloring only defined on some subset $I$ of $I(G)$. For every
uncolored incidence $(u,uv)\in I(G)\setminus I$, $F_{G}^{\phi^{\prime}}(u,uv)$
is defined by the set of forbidden colors of $(u,uv)$, that is:

$F_{G}^{\phi^{\prime}}(u,uv)=\phi^{\prime}(A_{u})\cup\phi^{\prime}(I_{u})\cup\phi^{\prime}(I_{v})$,

where $I_{u}$ is the set of incidences of the form $(u,uv)$ and $A_{u}$ is the
set of incidences of the form $(v,vu)$.

Note that the $(k,\ell)$-incidence coloring can also be seen in this setting
as a coloring $\phi$ of $G$ such that for every vertex $v\in V(G)$,
$\mid\phi(A_{v})\mid\leq\ell$.

###### Remark 1

Every $(k,\ell)$-incidence coloring of a graph is a
$(k^{\prime},\ell)$-incidence coloring for any $k^{\prime}>k$.

##  3 Proof of Theorem 7.1

###  3.1 Structural properties

We proceed by contradiction. Let $H$ be a counterexample to Theorem 7.1 that
minimizes $|E(H)|+|V(H)|$. By hypothesis there exists
$k\geq\max\\{\Delta(G),7\\}$ such that $H$ does not admit an incidence
$(k+3,3)$-coloring. Let $k\geq\max\\{\Delta(G),7\\}$ be the smallest integer
such that $H$ does not admit an incidence $(k+3,3)$-coloring. By using Remark
1 we must have $k=\max\\{\Delta(G),7\\}$. Moreover by minimality it is easy to
see that $H$ is connected.
$H$ satisfies the following properties:

###### Lemma 2

$H$ does not contain:

  1. 1.

a 1-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $3$-vertex adjacent to a $3$-vertex,

  4. 4.

a $((\Delta-2)^{-},(\Delta-1)^{-},\Delta^{-})$-vertex,

  5. 5.

a $(3,3,(\Delta-1)^{-},\Delta^{-})$-vertex,

  6. 6.

a $(3,4^{-},4^{-},4^{-})$-vertex.

Proof

Each of these 6 cases will be dealt with similarly. First, we suppose by
contradiction that the described configuration exists in $H$. Then we consider
a graph $H^{\prime}$ obtained from $H$ by deleting an edge or a vertex from
$H$. The graph $H^{\prime}$ has $\rm{mad}(H^{\prime})\leq\rm{mad}(H)<4$. Due
to the minimality of $H$, the graph $H^{\prime}$ admits an incidence
$(k^{\prime}+3,3)$-coloring for any
$k^{\prime}\geq\max\\{\Delta(H^{\prime}),7\\}$. Since
$\Delta(H)\geq\Delta(H^{\prime})$, the set of integers k’ contains the set of
integers k. Hence for the value $k^{\prime}=k$, $H^{\prime}$ admits an
incidence $(k+3,3)$-coloring $\phi^{\prime}$. Finally, for each case, we will
prove a contradiction by extending $\phi^{\prime}$ to an incidence
$(k+3,3)$-coloring $\phi$ of $H$.

  1. 1.

Suppose $H$ contains a $1$-vertex $u$ and let $v$ be its unique neighbor in
$H$. Consider $H^{\prime}=H-\\{u\\}$. $H^{\prime}$ admits an incidence
$(k+3,3)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$ to an
incidence $(k+3,3)$-coloring $\phi$ of $H$ as follows.
Since for all $v\in V(H^{\prime})$, $\mid\phi^{\prime}(A_{v})\mid\leq 3$, we
have

$\mid
F_{H}^{\phi^{\prime}}(v,vu)\mid=\mid\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})\cup\phi^{\prime}(I_{u})\mid\leq\Delta(H)-1+3+0=\Delta(H)+2\leq
k+2$

then there exists at least one color, say $\alpha$, such that $\alpha\notin
F_{H}^{\phi^{\prime}}(v,vu)$. Hence, we set $\phi(v,vu)=\alpha$ and one can
observe that $\mid\phi^{\prime}(A_{u})\mid=1\leq 3$. According to
$\mid\phi^{\prime}(A_{v})\mid\leq 3$, it suffices to set $\phi(u,uv)=\beta$
for any color $\beta$ in $\phi^{\prime}(A_{v})$ and we are done.
We have extended the coloring, a contradiction.

  2. 2.

Suppose $H$ contains a $2$-vertex $v$ and let $u$, $w$ be the two neighbors of
$v$ in $H$. By minimality of $H$, $H^{\prime}=H\setminus\\{v\\}$ admits an
incidence $(k+3,3)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+3,3)$-coloring $\phi$ of $H$ as follows.

$\mid
F_{H}^{\phi^{\prime}}(w,wv)\mid=\mid\phi^{\prime}(I_{w})\cup\phi^{\prime}(A_{w})\cup\phi^{\prime}(I_{v})\mid\leq\Delta(H)-1+3+0=\Delta(H)+2\leq
k+2$

Hence there is one available color to color $(w,wv)$, let $\phi(w,wv)=\beta$.
By doing the same calculation it is easy to see that there is one available
color to color $(u,uv)$, let $\phi(u,uv)=\alpha$. We have
$\mid\phi(A_{v})\mid=2\leq 3$. Consider now the following cases:

    1. (a)

If $\mid\phi^{\prime}(A_{u})\mid=3$ then we color $(v,vu)$ with a color
$\gamma\in\phi(A_{u})\setminus\\{\beta\\}$

    2. (b)

If $\mid\phi^{\prime}(A_{u})\mid\leq 2$ then we color $(v,vu)$ with a color
$\gamma\notin F_{H}^{\phi^{\prime}}(v,vu)$ different from $\beta$ (note that
we have two choices). One can observe that $\mid\phi(A_{u})\mid\leq 3$.

If $\mid\phi^{\prime}(A_{w})\mid=3$ then we color $(v,vw)$ with a color
$\zeta\in\phi(A_{w})\setminus\\{\alpha,\gamma\\}$ and we have
$\mid\phi(A_{w})\mid=3$. If $\mid\phi^{\prime}(A_{w})\mid\leq 2$ then we color
$(v,vw)$ with a color $\zeta\notin F_{H}^{\phi^{\prime}}(v,vw)$ (different
from $\alpha,\gamma$) and we have $\mid\phi(A_{w})\mid\leq 3$. We have
extended the coloring, a contradiction.

  3. 3.

Suppose $H$ contains a $3$-vertex $u$ adjacent to a $3$-vertex $v$. By
minimality of $H$, $H^{\prime}=H\setminus\\{uv\\}$ has an incidence
$(k+3,3)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$ to an
incidence $(k+3,3)$-coloring $\phi$ of $H$ as follows.

$\mid\phi^{\prime}(A_{u})\mid\leq 2$ and $\mid\phi^{\prime}(A_{v})\mid\leq 2$

$\mid
F_{H}^{\phi^{\prime}}(u,uv)\mid=\mid\phi^{\prime}(I_{u})\cup\phi^{\prime}(A_{u})\cup\phi^{\prime}(I_{v})\mid\leq
2+2+2=6$

We have at least $k-3\geq 4$ free colors for $(u,uv)$. Choose a color for
$(u,uv)$, then for $(v,vu)$ by using the same calculation at most 7 colors are
forbidden for this incidence. We have at least $k-4\geq 3$ free colors. That
is more than enough to extend the coloring, a contradiction.

  4. 4.

Suppose $H$ contains a $((\Delta-2)^{-},(\Delta-1)^{-},\Delta^{-})$-vertex $v$
and let $u_{1}$, $u_{2}$ and $u_{3}$ be the three neighbors of $v$ in $H$ such
that $d(u_{1})\leq\Delta-2$, $d(u_{2})\leq\Delta-1$ and $d(u_{3})\leq\Delta$.
Consider $H^{\prime}=H-\\{vu_{1}\\}$. By minimality of $H$, $H^{\prime}$
admits an incidence $(k+3,3)$-coloring $\phi^{\prime}$. We will extend
$\phi^{\prime}$ to an incidence $(k+3,3)$-coloring $\phi$ of $H$ as follows.

    1. $(1)$

If $\mid\phi^{\prime}(A_{u_{1}})\mid\leq 2$, then $\mid
F_{H}^{\phi^{\prime}}(v,vu_{1})\mid=\mid\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})\cup\phi^{\prime}(I_{u_{1}})\mid\leq
2+2+\Delta(H)-3=\Delta(H)+1\leq k+1$ then there exists at least one color, say
$\alpha$, such that $\alpha\notin F_{H}^{\phi^{\prime}}(v,vu_{1})$. Hence, we
set $\phi(v,vu_{1})=\alpha$ and we have $\mid\phi(A_{u_{1}})\mid\leq 2+1=3$.
For the incidence $(u_{1},u_{1}v)$, we have $\mid
F_{H}^{\phi^{\prime}}(u_{1},u_{1}v)\mid=\mid\phi^{\prime}(I_{u_{1}})\cup\phi^{\prime}(A_{u_{1}})\cup\phi^{\prime}(I_{v})\mid\leq\Delta(H)-3+3+2=\Delta(H)+2\leq
k+2$. Then there exists at least one color $\beta\notin
F_{H}^{\phi^{\prime}}({u_{1}},{u_{1}}v)$. Hence we color the incidence
$(u_{1},u_{1}v)$ with $\beta$.

    2. $(2)$

If $\mid\phi^{\prime}(A_{u_{1}})\mid=3$. We distinguish two cases :

       * $Case\leavevmode\nobreak\ 1.$

Suppose
$\phi^{\prime}(A_{u_{1}})\nsubseteq\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$,
then we have a color
$\alpha\in\phi^{\prime}(A_{u_{1}})\setminus\\{\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})\\}$.
We color $(v,vu_{1})$ with $\alpha$.

$\mid
F_{H}^{\phi^{\prime}}(u_{1},u_{1}v)\mid=\mid\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{u_{1}})\cup\phi^{\prime}(I_{u_{1}})\mid\leq
2+3+\Delta(H)-3=\Delta(H)+2\leq k+2$

Hence, there exists at least one available color $\beta\notin
F_{H}^{\phi^{\prime}}(u_{1},u_{1}vu)$, we set $\phi(u_{1},u_{1}v)=\beta$ and
we have $\mid\phi^{\prime}(A_{v})\mid\leq 3$.

       * $Case\leavevmode\nobreak\ 2.$

Suppose
$\phi^{\prime}(A_{u_{1}})\subseteq\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$.
W.l.o.g we assume that the available colors for $(v,vu_{1})$ of
$\phi^{\prime}(A_{u_{1}})$ are the colors $1$, $2$ and $3$. We must notice
that we have two available colors to color $(u_{2},u_{2}v)$, if we do not take
into account the constraints given by $\phi^{\prime}(I_{v})$. Then we have two
cases to consider.

         1. $A.$

$\phi^{\prime}(v,vu_{2})=1$, $\phi^{\prime}(v,vu_{3})=2$,
$\phi^{\prime}(u_{2},u_{2}v)=3$.

           1. $1.$

If we can change the color of $(u_{2},u_{2}v)$ in $\phi^{\prime}$ and
$\phi^{\prime}(u_{3},u_{3}v)\neq 3$, then we recolor the incidence
$(u_{2},u_{2}v)$ and we have
$3\notin\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$, then we proceed exactly
as $case\leavevmode\nobreak\ 1$.

           2. $2.$

If we can change the color of $(u_{2},u_{2}v)$ and
$\phi^{\prime}(u_{3},u_{3}v)=3$, then we recolor the incidence
$(u_{2},u_{2}v)$ with a color $a$ and it easy to see that $a\neq 1$ and $2$.
The list of the available colors of $(v,vu_{2})$ is
$L=\phi^{\prime}(A_{u_{2}})=\\{1,\alpha,\beta\\}$ and $3$ and $a$ are not
belonging to $L$. We recolor $(v,vu_{2})$ with a color different from $1$, $2$
and we have $1\notin\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$, then we
proceed exactly as $case\leavevmode\nobreak\ 1$.

           3. $3.$

If we cannot change the color of $(u_{2},u_{2}v)$, it means that the available
colors for $(u_{2},u_{2}v)$ are $3$ and $2$. The list of available colors for
$(v,vu_{2})$ is $L=\phi^{\prime}(A_{u_{2}})=\\{1,\alpha,\beta\\}$ and $3$, $2$
are not belonging to $L$. We color $(v,vu_{2})$ with a color different from
$1$ and $\phi^{\prime}(u_{3},u_{3}v)$. We have
$1\notin\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$, then we proceed exactly
as $case\leavevmode\nobreak\ 1$.

         2. $B.$

$\phi^{\prime}(v,vu_{2})=1$, $\phi^{\prime}(u_{2},u_{2}v)=2$,
$\phi^{\prime}(u_{3},u_{3}v)=3$ and $\phi^{\prime}(v,vu_{3})=b_{3}$ such that
$b_{3}\notin\\{1,2,3\\}$.

           1. $1.$

If we can change the color of $(u_{2},u_{2}v)$, then we recolor the incidence
$(u_{2},u_{2}v)$ and we have
$2\notin\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$, then we proceed exactly
as $case\leavevmode\nobreak\ 1$.

           2. $2.$

If we cannot change the color of $(u_{2},u_{2}v)$, it means that the available
colors for $(u_{2},u_{2}v)$ are $2$ and $b_{3}$. The list of available colors
for $(v,vu_{2})$ is $L=\phi^{\prime}(A_{u_{2}})=\\{1,\alpha,\beta\\}$ and
$b_{3}$, $2$ are not belonging to $L$. We color $(v,vu_{2})$ with a color
different from $1$ and $3$, we have
$1\notin\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})$, then we proceed exactly
as $case\leavevmode\nobreak\ 1$.

We have extended the coloring, a contradiction.

  5. 5.

Assume that $H$ contains a $(3,3,(\Delta-1)^{-},\Delta^{-})$-vertex $u$. Let
$u_{1},u_{2}$ be the two neighbors of $u$ having a degree equal to 3. Let $v$
be the vertex of degree $\Delta^{-}$ and $w$ the neighbor of degree
$(\Delta-1)^{-}$. We consider $H^{\prime}=H\setminus\\{u\\}$. By minimality of
$H$, $H^{\prime}$ has an incidence $(k+3,3)$-coloring $\phi^{\prime}$. By
using the same computation as above we have:

    1. (a)

at least one free color for $(v,vu)$.

    2. (b)

at least $2$ free colors for $(w,wu)$.

    3. (c)

at least $k-1\geq 6$ free colors for $(u_{i},u_{i}u)$, $i\in\\{1,2\\}$. We
denote by $L_{i}$ the list of available colors of $(u_{i},u_{i}u)$,
$i\in\\{1,2\\}$.

    4. (d)

at least $k+1\geq 8$ free colors for $(u,uu_{i})$, $i\in\\{1,2\\}$.

    5. (e)

a set of 3 free colors for $(u,uv)$ and a set of 3 free colors for $(u,uw)$
($\phi^{\prime}(A_{v})$ and $\phi^{\prime}(A_{w}))$.

Now we extend the coloring.
We first color $(v,vu)$. We have one free color $\alpha$ for $(v,vu)$. We
color $(v,vu)$ with $\alpha$.
Since $\mid L_{1}\mid=\mid L_{2}\mid=k-1$, there exists $\beta\in L_{1}\cap
L_{2}$. We color $(u_{i},u_{i}u)$, $i\in\\{1,2\\}$ with $\beta$. It is easy to
see that in the new coloring we will have $\mid\phi(A_{u})\mid\leq 3$.

Now we extend the coloring in the following order.

    1. (a)

We color $(u,uw)$ with a color $\phi(u,uw)$ different from $\alpha$ and
$\beta$.

    2. (b)

We color $(u,uv)$ with a color $\phi(u,uv)$ different from $\beta$ and
$\phi(u,uw)$.

    3. (c)

We color $(w,wu)$ with a color $\phi(w,wu)$ different from $\phi(u,uv)$.

    4. (d)

We color $(u,uu_{1})$ with a color $\phi(u,uu_{1})$ different from $\alpha$,
$\phi(u,uw)$, $\phi(u,uv)$, $\phi(w,wu)$.

    5. (e)

We color $(u,uu_{2})$ with a color $\phi(u,uu_{2})$ different from $\alpha$,
$\phi(u,uw)$, $\phi(u,uv)$, $\phi(w,wu)$ and $\phi(u,uu_{1})$.

Hence we extend the coloring, a contradiction. This completes the proof.

  6. 6.

Suppose $H$ contains a $(3,4^{-},4^{-},4^{-})$-vertex $u$. Let $v$ be the
neighbor of degree $3$, $u_{1},u_{2},u_{3}$ be the 3 neighbors of degree
$4^{-}$. We consider $H^{\prime}=H\setminus\\{u\\}$. By minimality of $H$,
$H^{\prime}$ has an incidence $(k+3,3)$-coloring $\phi^{\prime}$. By an easy
computation as above we have the following:

    1. (a)

Let $L(v)$ be the list of free colors for $(v,vu)$. Then $\mid
L(v)\mid=k-1\geq 6$.

    2. (b)

We denote by $L_{i}$ the list of available colors of each $(u_{i},u_{i}u)$
($i\in\\{1,2,3\\}$). Then $\mid L_{i}\mid=k-3\geq 4$.

    3. (c)

for each $i\in\\{1,2,3\\}$ we have a set of 3 available colors to color
$(u,uu_{i})$ ($\phi^{\prime}(A_{u_{i}})$ for $i\in\\{1,2,3\\}$).

    4. (d)

We have $k+1\geq 8$ available colors to color $(u,uv)$.

Since $\mid L_{i}\mid=k-3$ for $i\in\\{1,2,3\\}$. There exists at least two
lists having an element in commun. W.l.o.g. assume that $\alpha\in L_{1}\cap
L_{2}$. We color $(u_{1},u_{1}u)$ and $(u_{2},u_{2}u)$ with $\alpha$. It
follows that in any cases $\mid\phi(A_{v})\mid\leq 3$.
We extend now the coloring in the following order:

    1. (a)

$\phi(u,uu_{3})$ will be a color different from $\alpha$.

    2. (b)

$\phi(u,uu_{2})$ will be a color different from $\phi(u,uu_{3})$.

    3. (c)

$\phi(u,uu_{1})$ will be a color different from $\phi(u,uu_{2})$ and
$\phi(u,uu_{3})$.

    4. (d)

$\phi(u_{3},u_{3}u)$ will be a color different from $\phi(u,uu_{2})$ and
$\phi(u,uu_{1})$.

    5. (e)

$\phi(v,vu)$ will be a color different from $\phi(u,uu_{1})$, $\phi(u,uu_{2})$
and $\phi(u,uu_{3})$.

    6. (f)

$\phi(u,uv)$ will be a color different from $\alpha$, $\phi(v,vu)$,
$\phi(u_{3},u_{3}u)$ and $\phi(u,u_{i})$, $i\in\\{1,2,3\\}$.

Hence we extend the coloring in both cases, a contradiction. This completes
the proof.

$\Box$

###  3.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-4$. It follows from the hypothesis on the maximum average
degree that the total sum of weights is strictly negative. In the next step,
we define discharging rules (R1) to (R3) and we redistribute weights and once
the discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.

The discharging rules are defined as follows:

  1. (R1)

Every $k$-vertex, for $k\geq 5$, gives $\frac{k-4}{k}$ to each adjacent
$3$-vertex.

  2. (R2)

Every $k$-vertex, for $k\geq 5$, gives $\frac{k-4}{k}$ to each adjacent
$4$-vertices having neighbors of degree 3.

  3. (R3)

Every $4$-vertex gives uniformly (in equal parts) its its new weight to its
neighbors of degree 3.

Let $v\,\in\,V(H)$ be a $k$-vertex. By Lemma 2.1 and Lemma 2.2, $k\geq 3$.
Consider the following cases:

  1. Case $\boldsymbol{k=4.}$ Observe that $\omega(v)=0$. By Lemma 2.5, $v$ has at most 2 neighbors both of degree 3. If $v$ has no neighbor of degree 3, it gets nothing and it gives nothing and $\omega^{\ast}(v)=0$. We have now to consider 2 cases:

    1. (a)

If it has only one neighbor of degree 3 it has at least one neighbor having a
degree at least 5 by Lemma 2.6. Then it gets at least $\frac{1}{5}$ and it
gives this weight to its neighbor of degree 3. We have $\omega^{\ast}(v)=0$.

    2. (b)

If it has two neighbors of degree 3. Then it has two neighbors with degree at
least 7 by Lemma 2.5. Then it gets at least $2\times\frac{3}{7}$, hence it
gives at least $\frac{3}{7}$ to each of its neighbors of degree 3. We have
$\omega^{\ast}(v)=0$.

  2. Case $\boldsymbol{k=3.}$ Observe that $\omega(v)=-1$.

    1. (a)

$v$ has at most one neighbor of degree 4, if it is the case, its two other
neighbors have by Lemma 2.4 a degree at least 7. Hence
$\omega^{\ast}(v)\geq-1+\frac{1}{5}+2\times\frac{3}{7}=-1+\frac{37}{35}=\frac{2}{35}>0$

    2. (b)

If $v$ has a neighbor of degree 5 by Lemma 2.4 the two other neighbors have a
degree at least 7. Hence,
$\omega^{\ast}(v)\geq-1+\frac{1}{5}+2\times\frac{3}{7}=-1+\frac{37}{35}=\frac{2}{35}>0$

    3. (c)

If $v$ has no neighbor of degree less or equal to 5, we have
$\omega^{\ast}(v)\geq-1+3\times\frac{1}{3}=0$

  3. Case $\boldsymbol{k\geq 5.}$ The vertex $v$ satisfies $\omega^{\ast}(v)\geq k-4-k\times\frac{k-4}{k}\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. This completes the proof of Theorem
7.2.

###### Remark 2

In what follows we will assume, if we need it, that
$\mid\phi^{\prime}(A_{v})\mid=3$. If it is not the case, it is easy to see
that we can complete $\phi^{\prime}(A_{v})$ with colors not belonging to
$\phi^{\prime}(A_{v})\cup\phi^{\prime}(I_{v})$ in order to have
$\mid\phi^{\prime}(A_{v})\mid=3$.

##  4 Proof of Theorem 7.2

###  4.1 Structural properties

We proceed by contradiction. We will use the same reasoning than in the proof
of Theorem 7.1. Let $H$ be a counterexample to Theorem 7.2 that minimizes
$|E(H)|+|V(H)|$. By hypothesis there exists $k\geq\max\\{\Delta(G),9\\}$ such
that $H$ does not admit an incidence $(k+4,4)$-coloring. Let
$k\geq\max\\{\Delta(G),9\\}$ be the smallest integer such that $H$ does not
admit an incidence $(k+4,4)$-coloring. By using Remark 1 we must have
$k=\max\\{\Delta(G),9\\}$. Moreover by minimality it is easy to see that $H$
is connected.
$H$ satisfies the following properties:

###### Lemma 3

$H$ does not contain:

  1. 1.

a $1$-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $((\Delta-1)^{-},\Delta^{-},\Delta^{-})$-vertex,

  4. 4.

a $4$-vertex adjacent to a $4^{-}$-vertex,

  5. 5.

a $(5^{-},5^{-},5^{-},5^{-})$-vertex.

Proof

  1. 1-2.

By using the same method as in the proof of Theorem 7.1, it is easy to prove
the two first item of Lemma 3.

  2. 3.

Suppose $H$ contains a $((\Delta-1)^{-},\Delta^{-},\Delta^{-})$-vertex $v$ and
let $u_{1}$, $u_{2}$ and $u_{3}$ be the three neighbors of $v$ in $H$ such
that $d(u_{1})\leq\Delta-1$, $d(u_{2})\leq\Delta$ and $d(u_{3})\leq\Delta$.
Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$, $H^{\prime}$ admits an
incidence $(k+4,4)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+4,4)$-coloring $\phi$ of $H$ as follows.

We have:

$\mid
F_{H}^{\phi^{\prime}}(u_{1},u_{1}v)\mid=\mid\phi^{\prime}(I_{u_{1}})\cup\phi^{\prime}(A_{u_{1}})\cup\phi^{\prime}(I_{v})\mid\leq\Delta(H)-2+4+0=\Delta(H)+2\leq
k+2$

Hence there are 2 free colors $a$ and $b$ to color $(u_{1},u_{1}v)$. For the
incidences $(u_{i},u_{i}v)$, $i\in\\{2,3\\}$ we have at least one color for
each incidence. W.l.o.g we set $\phi(u_{2},u_{2}v)=c$ and
$\phi((u_{3},u_{3}v)=d$. For each $(v,vu_{i})$, $i\in\\{1,2,3\\}$, we have $4$
available colors: the colors of $\phi^{\prime}(A_{u_{i}})$.
First we color $(u_{1},u_{1}v)$ with the colors $a$. Then we color
$(v,vu_{2})$ with a color different from $a$ and $d$, we set
$\phi(v,vu_{2})=e$. We color $(v,vu_{3})$ with a color different from $a$, $c$
and $e$, we set $\phi(v,vu_{2})=f$. If we can color $(v,vu_{1})$, we are done.
So we cannot color $(v,vu_{1})$, it means that
$\phi^{\prime}(A_{u_{1}})=\\{c,d,e,f\\}$ (See Figure 1).

Figure 1: $(\Delta-1,\Delta,\Delta)$-vertex

If we can change the color of $(v,vu_{2})$ by taking one other available color
of $(v,vu_{2})$, we change the color of $(v,vu_{2})$ and we give the color $e$
to $(v,vu_{1})$ and we are done. Hence we cannot change the color of
$(v,vu_{2})$, it means that $\phi^{\prime}(A_{u_{2}})=\\{a,d,e,f\\}$. Then we
color $(u_{1},u_{1}v)$ with $b$ ($b$ is not belonging to
$\phi^{\prime}(A_{u_{1}})=\\{c,d,e,f\\}$), we color $(v,vu_{2})$ with $a$ and
$(v,vu_{1})$ with $e$, and we are done, a contradiction. This completes the
proof.

  3. 4.

Suppose $H$ contains $2$ adjacent 4 vertices $u$ and $v$.
Consider $H^{\prime}=H-\\{uv\\}$. By minimality of $H$, $H^{\prime}$ admits an
incidence $(k+4,4)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+4,4)$-coloring $\phi$ of $H$ as follows.
We have

$\mid
F_{H}^{\phi^{\prime}}(u,uv)\mid=\mid\phi^{\prime}(I_{u})\cup\phi^{\prime}(A_{u})\cup\phi^{\prime}(I_{v})\mid\leq
3+3+3=9\leq k$

and

$\mid
F_{H}^{\phi^{\prime}}(v,vu)\mid=\mid\phi^{\prime}(I_{v})\cup\phi^{\prime}(A_{v})\cup\phi^{\prime}(I_{u})\mid\leq
3+3+3=9\leq k$

For each incidence we have $4$ free colors. We can easly extend the
coloration, a contradiction. This completes the proof.

  4. 5.

Suppose $H$ contains a $(5^{-},5^{-},5^{-},5^{-})$-vertex $v$ and let $u_{1}$,
$u_{2}$, $u_{3}$ and $u_{4}$ be the 4 neighbors of $v$ in $H$ such that
$d(u_{i})=5$, for $i\in\\{1,2,3,4\\}$. Consider $H^{\prime}=H-\\{v\\}$. By
minimality of $H$, $H^{\prime}$ admits an incidence $(k+4,4)$-coloring
$\phi^{\prime}$.
We have

$\mid
F_{H}^{\phi^{\prime}}(u_{i},u_{i}v)\mid=\mid\phi^{\prime}(I_{u_{i}})\cup\phi^{\prime}(A_{u_{i}})\cup\phi^{\prime}(I_{v})\mid\leq
4+4=8\leq k-1$

Hence each incidence $(u_{i},u_{i}v)$ has least $5$ available colors.
Moreover each incidence $(v,vu_{i})$ has $4$ available colors
($\phi^{\prime}(A_{u_{i}})$). We will extend $\phi^{\prime}$ to an incidence
$(k+4,4)$-coloring $\phi$ of $H$ as follows.
We first color the incidence $(v,vu_{i})$ one after the other, next we color
the incidences $(u_{i},u_{i}v)$. We have $5$ available colors for each
$(u_{i},u_{i}v)$ and $3$ new forbidden colors. This completes the proof.

$\Box$

###  4.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-\frac{9}{2}$. It follows from the hypothesis on the maximum
average degree that the total sum of weights is strictly negative. In the next
step, we define a discharging rule (R) and we redistribute weights and once
the discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.
We recall:

  1. 1.

if $d(v)=3$, $\omega(v)=-\frac{3}{2}$,

  2. 2.

if $d(v)=4$, $\omega(v)=-\frac{1}{2}$,

  3. 3.

if $d(v)=5$, $\omega(v)=\frac{1}{2}$.

The discharging rule is defined as follows:

  1. (R)

Every $k$-vertex ($k\geq 5$) gives $\frac{2k-9}{2k}$ to each of its neighbors
having a degree less or equal to 4.

We have to notice that a $k$-vertex do not give more that it has. Let
$v\,\in\,V(H)$ be a $k$-vertex. By Lemma 3.1 and Lemma 3.2, $k\geq 3$.
Consider the following cases:

  1. Case $\boldsymbol{k=3.}$ Observe that $\omega(v)=-\frac{3}{2}$. By Lemma 3.3, $v$ has neighbors having a degree $\Delta\geq 9$. Hence we have: $\omega^{\ast}(v)\geq-\frac{3}{2}+3\times\frac{1}{2}=0$.

  2. Case $\boldsymbol{k=4.}$ Observe that by Lemma 3.4 and Lemma 3.5, it has at most 3 neighbors having degree 5. Hence: $\omega^{\ast}(v)\geq-\frac{1}{2}+3\times\frac{1}{10}+\frac{3}{12}=\frac{1}{20}\geq 0$.

  3. Case $\boldsymbol{k\geq 5.}$ The vertex $v$ satisfies $\omega^{\ast}(v)\geq k-\frac{9}{2}-k\times\frac{2k-9}{2k}\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. This completes the proof of Theorem
7.2.

##  5 Proof of Theorem 7.3

###  5.1 Structural properties

We proceed by contradiction. We use the same reasonnig as above. Let $H$ be a
counterexample to Theorem 7.3 that minimizes $|E(H)|+|V(H)|$. By hypothesis
there exists $k\geq\max\\{\Delta(G),9\\}$ such that $H$ does not admit an
incidence $(k+5,5)$-coloring. Let $k\geq\max\\{\Delta(G),9\\}$ be the smallest
integer such that $H$ does not admit an incidence $(k+5,5)$-coloring. By using
Remark 1 we must have $k=\max\\{\Delta(G),9\\}$. By minimality it is easy to
see that $H$ is connected.
$H$ satisfies the following properties:

###### Lemma 4

$H$ does not contain:

  1. 1.

a $1$-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $3$-vertex,

  4. 4.

a $4$-vertex adjacent to a $5^{-}$-vertex,

  5. 5.

a $4$-vertex adjacent to two $6$-vertices.

Proof

  1. 1-2.

By using the same method as in the proof of Theorem 7.1, it is easy to prove
the two first item of Lemma 4.

  2. 3.

Suppose $H$ contains a 3-vertex $v$ and let $u_{1},u_{2},u_{3}$ be the
neighbors of $v$. Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$,
$H^{\prime}$ admits an incidence $(k+5,5)$-coloring $\phi^{\prime}$. We will
extend $\phi^{\prime}$ to an incidence $(k+5,5)$-coloring $\phi$ of $H$ as
follows.
Each incidence $(u_{i},u_{i}v)$ has one avaible color, we color each incidence
$(u_{i},u_{i}v)$ with this available color. Each incidence $(v,vu_{i})$ has
$5$ available colors ($\phi^{\prime}(A_{u_{i}})$).We color each incidence
$(v,vu_{i})$ one after in other to have an incidence coloring. Hence we extend
the coloring, a contradition.

  3. 4.

Suppose $H$ contains a $4$-vertex $v$ adjacent to a $5^{-}$-vertex $u$.
Consider $H^{\prime}=H-\\{uv\\}$. By minimality of $H$, $H^{\prime}$ admits an
incidence $(k+5,5)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+5,5)$-coloring $\phi$ of $H$ as follows.
It is easy to see that:

    1. (a)

the incidence $(v,vu)$ has at least $k+5-10=k-5\geq 4$ free colors,

    2. (b)

the incidence $(u,uv)$ has at least $k+5-11=k-6\geq 3$ free colors.

It is easy to see that we can extend the coloring. The proof is left to the
reader.

  4. 5.

Suppose $H$ contains a 4-vertex $v$ having two neighbors $u_{1}$ and $u_{2}$
with $d(u_{1})=d(u_{2})=6$. Let $u_{3}$ and $u_{4}$ be the two other
neighbors. Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$, $H^{\prime}$
admits an incidence $(k+5,5)$-coloring $\phi^{\prime}$. We will extend
$\phi^{\prime}$ to an incidence $(k+5,5)$-coloring $\phi$ of $H$ as follows.
By using the same computation as above we have:

    1. (a)

at least one free color for $(u_{i},u_{i}v)$, $i\in\\{3,4\\}$. We color
$(u_{i},u_{i}v)$ with this free color. We set $\phi(u_{3},u_{3}v)=a$ and
$\phi(u_{4},u_{4}v)=b$.

    2. (b)

a set of 5 free colors for $(v,vu_{i})$, $i\in\\{1,2,3,4\\}$
($\phi^{\prime}(A_{u_{i}})$, $i\in\\{1,2,3,4\\}$). We color $(v,vu_{1})$ with
a color different from $a$ and $b$. We color $(v,vu_{2})$ with a color
different from $a$, $b$ and $\phi(v,vu_{1})$. We color $(v,vu_{3})$ with a
color different from $b$, $\phi(v,vu_{1})$ and $(v,vu_{2})$. We color
$(v,vu_{4})$ with a color different from $a$, $\phi(v,vu_{1})$,
$\phi(v,vu_{2})$ and $\phi(v,vu_{3})$.

    3. (c)

at least $k-5$ free colors for $(u_{i},u_{i}v)$, $i\in\\{1,2\\}$, so at least
$4$ free colors. We color $(u_{1},u_{1}v)$ with a color different from
$\phi(v,vu_{2})$, $\phi(v,vu_{3})$ and $\phi(v,vu_{4})$ and we color
$(u_{2},u_{2}v)$ with a color different from $\phi(v,vu_{1})$,
$\phi(v,vu_{3})$ and $\phi(v,vu_{4})$.

Hence we have extended the coloration to the whole graph $H$, a contradiction.
This completes the proof.

$\Box$

###  5.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-5$. It follows from the hypothesis on the maximum average
degree that the total sum of weights is strictly negative. In the next step,
we define a discharging rule (R) and we redistribute weights and once the
discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.
We recall that we have only one negative weight: $d(v)=4$, $\omega(v)=-1$.

The discharging rule is defined as follows:

  1. (R)

Every $k$-vertex ($k\geq 6$) gives $\frac{k-5}{k}$ to each of its neighbors
having a degree equal to 4.

We have to notice that a $k$-vertex ($k\geq 6$) does not give more that it
has. Let $v\,\in\,V(H)$ be a $k$-vertex. By Lemma 4.1, Lemma 4.2 and Lemma
4.3, $k\geq 4$. Consider the following cases:

  1. Case $\boldsymbol{k=4.}$ Observe that $\omega(v)=-1$. By Lemma 4.4 the neighbors of $v$ have a degree at least 6 and by Lemma 4.5, $v$ has at most one neighbor having a degree equal to $6$. Hence we have: $\omega^{\ast}(v)\geq-1+3\times\frac{2}{7}+\frac{1}{6}=-1+\frac{43}{42}=\frac{1}{42}\geq 0$.

  2. Case $\boldsymbol{k\geq 5.}$ The vertex $v$ satisfies $\omega^{\ast}(v)\geq k-5-k\times\frac{k-5}{k}\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. This completes the proof of Theorem
7.3.

##  6 Proof of Theorem 7.4

###  6.1 Structural properties

We proceed by contradiction. We use the same reasoning than prevously. Let $H$
be a counterexample to Theorem 7.4 that minimizes $|E(H)|+|V(H)|$. By
hypothesis there exists $k\geq\max\\{\Delta(G),7\\}$ such that $H$ does not
admit an incidence $(k+6,6)$-coloring. Let $k\geq\max\\{\Delta(G),7\\}$ be the
smallest integer such that $H$ does not admit an incidence $(k+6,6)$-coloring.
By using Remark 1 we must have $k=\max\\{\Delta(G),7\\}$. By minimality it is
easy to see that $H$ is connected.
$H$ satisfies the following properties:

###### Lemma 5

$H$ does not contain:

  1. 1.

a $1$-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $3$-vertex,

  4. 4.

a $((\Delta-1)^{-},\Delta^{-},\Delta^{-},\Delta^{-})$-vertex.

Proof

  1. 1-3.

By using the same method as in the proof of Theorem 7.1 and Theorem 7.3, it is
easy to prove the three first item of Lemma 5.

  2. 4.

Suppose $H$ contains a
$((\Delta-1)^{-},\Delta^{-},\Delta^{-},\Delta^{-})$-vertex $v$ and let
$u_{1}$, $u_{2}$, $u_{3}$ and $u_{4}$ be the four neighbors of $v$ in $H$ such
that $d(u_{1})\leq\Delta-1$, $d(u_{i})\leq\Delta$ for $i\in\\{2,3,4\\}$.
Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$, $H^{\prime}$ admits an
incidence $(k+6,6)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+6,6)$-coloring $\phi$ of $H$ as follows.
By using the same computation as above we have:

    1. (a)

for each $(u_{i},u_{i}v)$, $i\in\\{2,3,4\\}$, there is at least one free
color.

    2. (b)

at least two free colors for $(u_{1},u_{1}v)$,

    3. (c)

at least $6$ free colors for $(v,vu_{i})$, $i\in\\{1,2,3,4\\}$
($\phi^{\prime}(A_{u_{i}})$,$i\in\\{1,2,3,4\\}$).

We extend the incidence coloring as follows:

    1. (a)

We color each $(u_{i},u_{i}v)$, $i\in\\{2,3,4\\}$ with its free color. We set:
$\phi(u_{2},u_{2}v)=a$, $\phi(u_{3},u_{3}v)=b$ and $\phi(u_{4},u_{4}v)=c$.

    2. (b)

W.l.o.g. we assume that $\\{d,e\\}$ are the available colors for
$(u_{1},u_{1}v)$. We set $\phi(u_{1},u_{1}v)=d$.

    3. (c)

We color $(v,vu_{2})$ with a color different from $b$, $c$ and $d$, we set
$\phi(v,vu_{2})=1$.

    4. (d)

We color $(v,vu_{3})$ with a color different from $a$, $c$, $d$ and
$\phi(v,vu_{2})=1$. We set $\phi(v,vu_{3})=2$.

    5. (e)

We color $(v,vu_{4})$ with a color different from $a$, $b$, $d$,
$\phi(v,vu_{2})=1$ and $\phi(v,vu_{3})=2$. We set $\phi(v,vu_{4})=3$.

    6. (f)

If we have one available color for $(v,vu_{1})$ among its 6 free colors. We
are done.

    7. (g)

If we cannot color $(v,vu_{1})$, it means that the list of free colors of
$(v,vu_{1})$ is $\\{1,2,3,a,b,c\\}=\phi^{\prime}(A_{u_{1}})$. If we can take
an other free color for $(v,vu_{2})$, without destroying our incidence
coloring, we change the color of $(v,vu_{2})$ and color $(v,vu_{1})$ with $1$.
Hence we cannot change the color of $(v,vu_{2})$. So the set of free colors of
$(v,vu_{2})$ is $\\{1,2,3,b,c,d\\}=\phi^{\prime}(A_{u_{2}})$.

    8. (h)

We set $\phi(u_{1},u_{1}v)=e\notin\\{1,2,3,a,b,c\\}=\phi^{\prime}(A_{u_{1}})$,
$\phi(v,vu_{2})=d$ and $\phi(v,vu_{1})=1$ and we are done.

We have extended the coloring to $H$, a contradiction. This completes the
proof.

$\Box$

###  6.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-5$. It follows from the hypothesis on the maximum average
degree that the total sum of weights is strictly negative. In the next step,
we define a discharging rule (R) and we redistribute weights and once the
discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.
We recall that we have only one negative weight: $d(v)=4$, $\omega(v)=-1$.

The discharging rule is defined as follows:

  1. (R)

Every $k$-vertex ($k\geq 6$) gives $\frac{k-5}{k}$ to each of its neighbors
having a degree equal to 4.

We have to notice that a $k$-vertex ($k\geq 6$) does not give more that it
has. Let $v\,\in\,V(H)$ be a $k$-vertex. By Lemma 5.1, Lemma 5.2 and Lemma
5.3, $k\geq 4$. Consider the following cases:

  1. Case $\boldsymbol{k=4.}$ Observe that $\omega(v)=-1$. By Lemma 5.4, $v$ has four neighbors of degree equal to $\Delta\geq 7$. Hence we have: $\omega^{\ast}(v)\geq-1+4\times\frac{2}{7}=\frac{1}{7}\geq 0$.

  2. Case $\boldsymbol{k\geq 5.}$ The vertex $v$ satisfies $\omega^{\ast}(v)\geq k-5-k\times\frac{k-5}{k}\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. Hence we have proved the first
sentance of Theorem 7.4. Now by Theorem 1 if $\Delta\leq 6$, $\chi_{i}(G)\leq
2\Delta\leq\Delta+6$. This completes the proof of Theorem 7.4.

##  7 Proof of Theorem 7.5

###  7.1 Structural properties

We proceed by contradiction. We use the same reasoning than prevously. Let $H$
be a counterexample to Theorem 7.5 that minimizes $|E(H)|+|V(H)|$. By
hypothesis there exists $k\geq\max\\{\Delta(G),12\\}$ such that $H$ does not
admit an incidence $(k+6,6)$-coloring. Let $k\geq\max\\{\Delta(G),12\\}$ be
the smallest integer such that $H$ does not admit an incidence
$(k+6,6)$-coloring. By using Remark 1 we must have $k=\max\\{\Delta(G),12\\}$.
By minimality it is easy to see that $H$ is connected.
$H$ satisfies the following properties:

###### Lemma 6

$H$ does not contain:

  1. 1.

a $1$-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $3$-vertex,

  4. 4.

a $((\Delta-1)^{-},\Delta^{-},\Delta^{-},\Delta^{-})$-vertex,

  5. 5.

a $(8^{-},8^{-},8^{-},\Delta^{-},\Delta^{-})$-vertex.

Proof

  1. 1-3.

By using the same method as in the proof of Theorem 7.1 and Theorem 7.3, it is
easy to prove the three first item of Lemma 6.

  2. 4.

Suppose $H$ contains a
$((\Delta-1)^{-},\Delta^{-},\Delta^{-},\Delta^{-})$-vertex $v$. We proceed as
in the proof of Theorem 7.4, Lemma 5.4.

  3. 5.

Suppose $H$ contains a $(8^{-},8^{-},8^{-},\Delta^{-},\Delta^{-})$-vertex $v$.
Let $u_{1}$, $u_{2}$, $u_{3}$ be the $3$ neighbors of $v$ in $H$ having a
degree equal to 8, let $u_{4}$ and $u_{5}$ be the two neighbors of $v$ in $H$
such that $d(u_{4})\leq\Delta$, $d(u_{5})\leq\Delta$. Consider
$H^{\prime}=H-\\{v\\}$. By minimality of $H$, $H^{\prime}$ admits an incidence
$(k+6,6)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$ to an
incidence $(k+6,6)$-coloring $\phi$ of $H$ as follows.
By using the same computation as above we have:

    1. (a)

For each incidence $(u_{i},u_{i}v)$, $i\in\\{1,2,3\\}$

$\mid
F_{H}^{\phi^{\prime}}(u_{i},u_{i}v)\mid=\mid\phi^{\prime}(I_{u_{i}})\cup\phi^{\prime}(A_{u_{i}})\cup\phi^{\prime}(I_{v})\mid\leq
7+6+0=13$

It implies that we have at least $5$ free colors for each incidence
$(u_{i},u_{i}v)$, $i\in\\{1,2,3\\}$.

    2. (b)

for each $(u_{i},u_{i}v)$, $i\in\\{4,5\\}$, there is at least one free color.

    3. (c)

at least $6$ free colors for $(v,vu_{i})$, $i\in\\{1,2,3,4,5\\}$
($\phi^{\prime}(A_{u_{i}})$, $i\in\\{1,2,3,4,5\\}$).

We extend the incidence coloring as follows:

    1. (a)

First we color the incidence $(u_{i},u_{i}v)$, $i\in\\{4,5\\}$ with the free
color, we set $\phi(u_{4},u_{4}v)=a$ and $\phi(u_{5},u_{5}v)=b$.

    2. (b)

We color $(v,vu_{1})$ with a color $\phi(v,vu_{1})$ different from $a$ and
$b$.

    3. (c)

We color $(v,vu_{2})$ with a color $\phi(v,vu_{2})$ different from $a$, $b$
and $\phi(v,vu_{1})$.

    4. (d)

We color $(v,vu_{3})$ with a color $\phi(v,vu_{3})$ different from $a$, $b$,
$\phi(v,vu_{1})$ and $\phi(v,vu_{2})$.

    5. (e)

We color $(v,vu_{4})$ with a color $\phi(v,vu_{4})$ different from $b$,
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$ and $\phi(v,vu_{3})$.

    6. (f)

We color $(v,vu_{5})$ with a color $\phi(v,vu_{5})$ different from $a$,
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$, $\phi(v,vu_{3})$ and $\phi(v,vu_{4})$.

    7. (g)

We color each $(u_{i},u_{i}v)$, $i\in\\{1,2,3\\}$ with a color different from
the $4$ new forbidden colors incident to $v$.

We have extended the coloring to $H$, a contradiction. This completes the
proof.

$\Box$

###  7.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-6$. It follows from the hypothesis on the maximum average
degree that the total sum of weights is strictly negative. In the next step,
we define a discharging rule (R) and we redistribute weights and once the
discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.
We recall that we have :

  * 1.

$d(v)=4$, $\omega(v)=-2$

  * 2.

$d(v)=5$, $\omega(v)=-1$

The discharging rule is defined as follows:

  1. (R)

Every $k$-vertex ($k\geq 7$) gives $\frac{k-6}{k}$ to each of its neighbors
having a degree equal to 4 or 5.

We have to notice that a $k$-vertex ($k\geq 7$) does not give more that it
has. Let $v\,\in\,V(H)$ be a $k$-vertex. By Lemma 6.1, Lemma 6.2 and Lemma
6.3, $k\geq 4$. Consider the following cases:

  1. Case $\boldsymbol{k=4.}$ Observe that $\omega(v)=-2$. By Lemma 6.4, $v$ has four neighbors of degree equal to $\Delta\geq 12$. Hence we have: $\omega^{\ast}(v)\geq-2+4\times\frac{1}{2}=0$.

  2. Case $\boldsymbol{k=5.}$ $\omega^{\ast}(v)\geq 0$. Observe that $\omega(v)=-1$. By Lemma 6.5, $v$ has at least 3 neighbors of degree equal to $9$. Hence we have: $\omega^{\ast}(v)\geq-1+3\times\frac{1}{3}=0$.

  3. Case $\boldsymbol{k\geq 6.}$ The vertex $v$ satisfies $\omega^{\ast}(v)\geq k-6-k\times\frac{k-6}{k}\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. This completes the proof of Theorem
7.5.

##  8 Proof of Theorem 7.6

###  8.1 Structural properties

We proceed by contradiction. Let $H$ be a counterexample to Theorem 7.6 that
minimizes $|E(H)|+|V(H)|$. By hypothesis there exists
$k\geq\max\\{\Delta(G),8\\}$ such that $H$ does not admit an incidence
$(k+7,7)$-coloring. Let $k\geq\max\\{\Delta(G),8\\}$ be the smallest integer
such that $H$ does not admit an incidence $(k+7,7)$-coloring. By using Remark
1 we must have $k=\max\\{\Delta(G),8\\}$. By minimality it is easy to see that
$H$ is connected.
$H$ satisfies the following properties:

###### Lemma 7

$H$ does not contain:

  1. 1.

a $1$-vertex,

  2. 2.

a $2$-vertex,

  3. 3.

a $3$-vertex,

  4. 4.

a $4$-vertex,

  5. 5.

a $5$-vertex adjacent to a $6^{-}$-vertex,

  6. 6.

a $(5,5,5,5,5,5,\Delta^{-})$-vertex.

Proof

  1. 1-3.

By using the same method as in the proof of Theorem 7.1 and Theorem 7.3, it is
easy to prove the three first item of Lemma 7.

  2. 4.

Suppose $H$ contains a 4-vertex $v$ and let $u_{1},u_{2},u_{3},u_{4}$ be the
neighbors of $v$. Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$,
$H^{\prime}$ admits an incidence $(k+7,7)$-coloring $\phi^{\prime}$. We will
extend $\phi^{\prime}$ to an incidence $(k+7,7)$-coloring $\phi$ of $H$ as
follows.
Each incidence $(u_{i},u_{i}v)$ $i\in\\{1,2,3,4\\}$ has one avaible color, we
color each incidence $(u_{i},u_{i}v)$ with this available color. Each
incidence $(v,vu_{i})$ has $7$ available colors ($\phi^{\prime}(A_{u_{i}})$).
We color each incidence $(v,vu_{i})$ one after the other in order to have an
incidence coloring. Hence we extend the coloring, a contradition.

  3. 5.

Suppose $H$ contains a $5$-vertex $v$ adjacent to a $6^{-}$-vertex $u$.
Consider $H^{\prime}=H-\\{uv\\}$. By minimality of $H$, $H^{\prime}$ admits an
incidence $(k+7,7)$-coloring $\phi^{\prime}$. We will extend $\phi^{\prime}$
to an incidence $(k+7,7)$-coloring $\phi$ of $H$ as follows.
We have:

$\mid
F_{H}^{\phi^{\prime}}(u,uv)\mid=\mid\phi^{\prime}(I_{u})\cup\phi^{\prime}(A_{u})\cup\phi^{\prime}(I_{v})\mid\leq
5+5+4=14$

Since we have at least 15 colors, we have at least one available color for
$(u,uv)$. Moreover we allow by hypothesis 7 colors for $\phi(A_{v})$ and
$\mid\phi^{\prime}(A_{v})\mid\leq 4$. Hence we can color $(u,uv)$ with the
free color that it has. Since $\mid\phi^{\prime}(A_{v})\mid\leq 5$, there are
at least 1 free colors for the incidence $(v,vu)$.
It is then easy to extend the coloring to the whole graph $H$. A
contradiction.

  4. 6.

Suppose $H$ contains a $(5,5,5,5,5,5,\Delta^{-})$-vertex $v$. Let $u_{i}$,
$i\in\\{1,2,3,4,5,6\\}$ be the $6$ neighbors of $v$ in $H$ having a degree
equal to 5, let $u_{7}$ be the neighbors of $v$ in $H$ such that
$d(u_{7})\leq\Delta$. Consider $H^{\prime}=H-\\{v\\}$. By minimality of $H$,
$H^{\prime}$ admits a $(k+7,7)$-incidence coloring $\phi^{\prime}$. We will
extend $\phi^{\prime}$ to an incidence $(k+7,7)$-coloring $\phi$ of $H$ as
follows.
By using the same computation as above we have:

    1. (a)

For each incidence $(u_{i},u_{i}v)$, $i\in\\{1,2,3,4,5,6\\}$

$\mid
F_{H}^{\phi^{\prime}}(u_{i},u_{i}v)\mid=\mid\phi^{\prime}(I_{u_{i}})\cup\phi^{\prime}(A_{u_{i}})\cup\phi^{\prime}(I_{v})\mid\leq
4+4+0=8$

It implies that we have at least $7$ free colors for each incidence
$(u_{i},u_{i}v)$, $i\in\\{1,2,3,4,5,6\\}$.

    2. (b)

for $(u_{7},u_{7}v)$, there is at least one free color.

    3. (c)

at least $7$ free colors for $(v,vu_{i})$, $i\in\\{1,2,3,4,5,6,7\\}$
($\phi^{\prime}(A_{u_{i}})$, $i\in\\{1,2,3,4,5,6,7\\}$).

We extend the incidence coloring as follows:

    1. (a)

First we color the incidence $(u_{7},u_{7}v)$, with the free color, we set
$\phi(u_{7},u_{7}v)=a$.

    2. (b)

We color $(v,vu_{1})$ with a color $\phi(v,vu_{1})$ different from $a$.

    3. (c)

We color $(v,vu_{2})$ with a color $\phi(v,vu_{2})$ different from $a$,
$\phi(v,vu_{1})$.

    4. (d)

We color $(v,vu_{3})$ with a color $\phi(v,vu_{3})$ different from $a$,
$\phi(v,vu_{1})$ and $\phi(v,vu_{2})$.

    5. (e)

We color $(v,vu_{4})$ with a color $\phi(v,vu_{4})$ different from $a$,
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$ and $\phi(v,vu_{3})$.

    6. (f)

We color $(v,vu_{5})$ with a color $\phi(v,vu_{5})$ different from $a$,
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$, $\phi(v,vu_{3})$ and $\phi(v,vu_{4})$.

    7. (g)

We color $(v,vu_{6})$ with a color $\phi(v,vu_{6})$ different from $a$,
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$, $\phi(v,vu_{3})$ and $\phi(v,vu_{4})$ and
$\phi(v,vu_{5})$.

    8. (h)

We color $(v,vu_{7})$ with a color $\phi(v,vu_{7})$ different from
$\phi(v,vu_{1})$, $\phi(v,vu_{2})$, $\phi(v,vu_{3})$ and $\phi(v,vu_{4})$ and
$\phi(v,vu_{5})$ and $\phi(v,vu_{6})$.

    9. (i)

We color each $(u_{i},u_{i}v)$, $i\in\\{1,2,3,5,6\\}$ with a color different
from the $6$ new forbidden colors incident to $v$.

We have extended the coloring to $H$, a contradiction. This completes the
proof.

$\Box$

###  8.2 Discharging procedure

We define the weight function $\omega:V(H)\rightarrow\mathbb{R}$ with
$\omega(x)=d(x)-6$. It follows from the hypothesis on the maximum average
degree that the total sum of weights is strictly negative. In the next step,
we define a discharging rules (R1), (R2) and we redistribute weights and once
the discharging is finished, a new weight function $\omega^{\ast}$ will be
produced. During the discharging process the total sum of weights is kept
fixed. Nevertheless, we can show that $\omega^{\ast}(x)\geq 0$ for all
$x\,\in\,V(H)$. This leads to the following contradiction:

$0\;\leq\sum_{x\,\in\,V(H)}\;\omega^{\ast}(x)\;=\;\sum_{x\,\in\,V(H)}\;\omega(x)\;<\;0$

and hence, this counterexample cannot exist.
We recall that we have only one negative weight: $d(v)=5$, $\omega(v)=-1$.

The discharging rules are defined as follows:

  1. (R1)

Every $7$-vertex gives $\frac{1}{5}$ to each of its neighbors having a degree
equal to $5$.

  2. (R2)

Every $k$-vertex ($k\geq 8$) gives $\frac{k-6}{k}$ to each of its neighbors
having a degree equal to $5$.

We have to notice that a $k$-vertex ($k\geq 8$) does not give more that it
has. Moreover a $7$-vertex has at most $5$ neighbors of degree 5. Let
$v\,\in\,V(H)$ be a $k$-vertex. By Lemma 7.1, Lemma 7.2, Lemma 7.3 and Lemma
7.4 we have $k\geq 5$. Consider the following cases:

  1. Case $\boldsymbol{k=5.}$ Observe that $\omega(v)=-1$. By Lemma 7.5, $v$ has 5 neighbors of degree greater or equal to 7. Hence we have: $\omega^{\ast}(v)\geq-1+5\times\frac{1}{5}=0$.

  2. Case $\boldsymbol{k=6.}$ $\omega(v)=0$, $v$ has weight 0 and gives nothing. $\omega^{\ast}(v)=0$,

  3. Case $\boldsymbol{k=7.}$ $\omega(v)=1$ and $\omega^{\ast}(v)\geq 1-5\times\frac{1}{5}=0$, $v$ has at most 5 neighbors of degree 5 by Lemma 7.6.

  4. Case $\boldsymbol{k\geq 8.}$ $v$ does not give more that it has. $\omega^{\ast}(v)\geq 0$.

After performing the discharging procedure the new weights of all vertices are
positive and therefore, $H$ cannot exist. Hence we have proved the first
sentance of Theorem 7.6. Now by Theorem 1 if $\Delta\leq 7$, we have
$\chi_{i}(G)\leq 2\Delta\leq\Delta+7$. This completes the proof of Theorem
7.6.

###### Remark 3

By using Theorem 1 or the result of [8], the result of Theorem 7.1 is true for
$\Delta\leq 3$. More precisely every graph with $\Delta(G)\leq 3$, admits an
incidence $(\Delta(G)+3,3)$-coloring. The question remains open for graphs
with maximal degree $4$, $5$ or $6$ and a maximal average degree less than
$4$. A similar question can be asked for the other results of Theorem 7.

## References

  * [1] I. Algor, N. Alon, The star arboricity of graphs, _Discrete Mathematics_ , 75 : 11–22, 1989.
  * [2] M. Bonamy, B. Lévêque and A. Pinlou, 2-Distance Coloring of Sparse Graphs, _Journal of Graph Theory_ , DOI: 10.1002/jgt.21782, 2014
  * [3] R.A. Brualdi and J.J.Q. Massey, Incidence and strong edge colorings of graphs, _Discrete Mathematics_ , 122: 51–58, 1993.
  * [4] B. Guiduli, On incidence coloring and star arboricity of graphs, _Discrete Mathematics_ , 163: 275–278, 1997.
  * [5] M. Hosseini Dolama, E. Sopena and X. Zhu, Incidence coloring of $k$-degenerate graphs, _Discrete Mathematics_ , 283: 121–128, 2004.
  * [6] M. Hosseini Dolama and E. Sopena, On the maximum average degree and the incidence chromatic number of a graph, _Discrete Mathematics and Theoretical Computer Science_ , 7: 203–216, 2005.
  * [7] T.R. Jensen, B. Toft, Choosability versus chromaticity, _Geombinatorics_ , 5 (1995): 45–64.
  * [8] M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree $3$, _Discrete Mathematics_ , 292: 131–141, 2005.
  * [9] D. Yang, Fractional incidence coloring and star arboricity of graphs, _Ars Combin._ , 105:213-224, 2012(written in 2007).