1Department of Mathematics [Semnan] (Faculty of Mathematics, Statistics and Computer Science Semnan University P.O. Box: 35195-363 Semnan, Iran Zip Code: 35131-19111 - Iran)
Abstract : 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).
https://hal.inria.fr/hal-00959037
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
<>
Soumis le : jeudi 13 mars 2014 - 17:08:32
Dernière modification le : jeudi 11 janvier 2018 - 06:20:16
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:17:25
Mohammad Hosseini Dolama, Eric Sopena. On the maximum average degree and the incidence chromatic number of a graph. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.203-216. 〈hal-00959037〉
