Portal de Periódicos da CAPES

r -hued coloring of sparse graphs

2017; Elsevier BV; Volume: 237; Linguagem: Inglês

10.1016/j.dam.2017.11.033

1872-6771

Jian Cheng, Hong‐Jian Lai, Kate Lorenzen, Rong Luo, Joshua C. Thompson, Cun‐Quan Zhang,

Graph Labeling and Dimension Problems

For two positive integers k,r, a (k,r)-coloring (or r-hued k-coloring) of a graph G is a proper k-vertex-coloring such that every vertex v of degree dG(v) is adjacent to at least min{dG(v),r} distinct colors. The r-hued chromatic number, χr(G), is the smallest integer k for which G has a (k,r)-coloring. The maximum average degree of G, denoted by mad (G), equals max{2|E(H)|∕|V(H)|: H is a subgraph of G}. In this paper, we prove the following results using the well-known discharging method. For a graph G, if mad (G)<125, then χ3(G)≤6; if mad (G)<73, then χ3(G)≤5; if G has no C5-components and mad (G)<83, then χ2(G)≤4.