Mohammad Hosseini Dolama ; Eric Sopena - On the maximum average degree and the incidence chromatic number of a graph

dmtcs:349 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.349
On the maximum average degree and the incidence chromatic number of a graphArticle

Authors: Mohammad Hosseini Dolama 1; Eric Sopena ORCID2

  • 1 Department of Mathematics [Semnan]
  • 2 Laboratoire Bordelais de Recherche en Informatique

We prove that the incidence chromatic number of every 3-degenerated graph G is at most Δ (G)+4. It is known that the incidence chromatic number of every graph G with maximum average degree mad(G)<3 is at most Δ (G)+3. We show that when Δ (G) ≥ 5, this bound may be decreased to Δ (G)+2. Moreover, we show that for every graph G with mad(G)<22/9 (resp. with mad(G)<16/7 and Δ (G)≥ 4), this bound may be decreased to Δ (G)+2 (resp. to Δ (G)+1).


Volume: Vol. 7
Published on: January 1, 2005
Imported on: March 26, 2015
Keywords: planar graph,maximum average degree,incidence coloring,k-degenerated graph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

4 Documents citing this article

Consultation statistics

This page has been seen 277 times.
This article's PDF has been downloaded 575 times.