Injective Colorings of Graphs with Low Average Degree

Injective Colorings of Graphs with Low Average Degree

0.00 Avg rating0 Votes
Article ID: iaor20114266
Volume: 60
Issue: 3
Start Page Number: 553
End Page Number: 568
Publication Date: Jul 2011
Journal: Algorithmica
Authors: , ,
Keywords: graph coloring
Abstract:

Let mad(G) denote the maximum average degree (over all subgraphs) of G and let χ i (G) denote the injective chromatic number of G. We prove that if Δ≥4 and mad ( G ) Unknown character 14 5 equ1 , then χ i (G)≤Δ+2. When Δ=3, we show that mad ( G ) Unknown character 36 13 equ2 implies χ i (G)≤5. In contrast, we give a graph G with Δ=3, mad ( G ) = 36 13 equ3 , and χ i (G)=6.

Reviews

Required fields are marked *. Your email address will not be published.