Skip to Main content Skip to Navigation
Journal articles

On the maximum average degree and the incidence chromatic number of a graph

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).
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00959037
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 5:08:32 PM
Last modification on : Wednesday, September 9, 2020 - 2:42:27 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:17:25 PM

File

dm070112.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00959037, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

265

Files downloads

2469