Discrete Mathematics & Theoretical Computer Science · 2005 · 22 citations · 21 references
Natural SciencesBiologyColor TheoryCombinatoricsGraph VisualizationDirected Acyclic GraphsGraph AlgorithmsGraph Theory
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).
21
Choice Reviews Online · 1995 · 1.3K citations
On the complexity of H-coloring
Pavol Hell, Jaroslav Nešetřil · Journal of Combinatorial Theory Series B · 1990 · 671 citations
On acyclic colorings of planar graphs
O. V. Borodin · Discrete Mathematics · 2006 · 236 citations