On r-hued coloring of K 4-minor free graphs

Huimin Song, Suohai Fan, Y. Chen, Lei Sun, Hong Jian Lai

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

A list assignment L of G is a mapping that assigns every vertex vâ̂̂V(G) a set L(v) of positive integers. For a given list assignment L of G, an (L,r)-coloring of G is a proper coloring c such that for any vertex v with degree d(v), c(v)â̂̂L(v) and v is adjacent to at least min{d(v),r} different colors. The r-hued chromatic number of G, χr(G), is the least integer k such that for any vâ̂̂V(G) with L(v)={1,2,.,k}, G has an (L,r)-coloring. The r-hued list chromatic number of G, χL,r(G), is the least integer k such that for any vâ̂̂V(G) and every list assignment L with |L(v)|=k, G has an (L,r)-coloring. Let K(r)=r+3 if 2≤r≤3, and K(r)=⌊3r/2âŒ+1 if r≥4. We proved that if G is a K4-minor free graph, thenχr(G)≤K(r), and the bound can be attained;χL,r(G)≤K(r)+1. This extends a former result in Lih et al. (2003).

Original languageEnglish (US)
Pages (from-to)47-52
Number of pages6
JournalDiscrete Mathematics
Volume315-316
Issue number1
DOIs
StatePublished - 2014
Externally publishedYes

Keywords

  • (k, r)-coloring
  • Planar graph
  • r-hued coloring
  • r-hued list coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On r-hued coloring of K 4-minor free graphs'. Together they form a unique fingerprint.

Cite this