Name
Abstract | ||
|---|---|---|
AbstractA listassignment of G is a function L that assigns to each vertex $$v\in V(G)$$vźV(G) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring $$\phi $$ź such that for any vertex v with degree d(v), $$\phi (v)\in L(v)$$ź(v)źL(v) and v is adjacent to at least $$ min\{d(v),r\}$$min{d(v),r} different colors. The listr-huedchromaticnumber of G, $$\chi _{L,r}(G)$$źL,r(G), is the least integer k such that for every list assignment L with $$|L(v)|=k$$|L(v)|=k, $$v\in V(G)$$vźV(G), G has an (L, r)-coloring. We show that if $$r\ge 32$$rź32 and G is a planar graph without 4-cycles, then $$\chi _{L,r}(G)\le r+8$$źL,r(G)≤r+8. This result implies that for a planar graph with maximum degree $$\varDelta \ge 26$$Δź26 and without 4-cycles, Wagner's conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-017-0118-0 | Periodicals |
Keywords | DocType | Volume |
r-hued coloring,List r-hued coloring,Planar graphs,Wagner's conjecture | Journal | 34 |
Issue | ISSN | Citations |
3 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haiyang Zhu | 1 | 46 | 7.05 |
| Sheng Chen | 2 | 56 | 11.04 |
| Lianying Miao | 3 | 11 | 2.56 |
| Xinzhong Lv | 4 | 0 | 0.34 |