List version of L ( d , s ) -labelings Artikel uri icon

Open Access

  • true

Peer Reviewed

  • true

Abstract

  • Let G = ( V , E ) be a simple graph, and for all v ∈ V , let L ( v ) be a list of colors assigned to v . We shall assume throughout that the colors are natural numbers. For nonnegative integers d , s , define χ ℓ d , s ( G ) to be the smallest integer k such that for every list assignment with | L ( v ) | = k for all v ∈ V one can choose a color c ( v ) ∈ L ( v ) for every vertex in such a way that | c ( v ) - c ( w ) | ⩾ d for all vw ∈ E and | c ( v ) - c ( w ) | ⩾ s for all pairs v , w of vertices having distance 2 in G. For a given list assignment such a coloring c is called an L ( d , s ) -list labeling. We prove a general bound for χ ℓ d , s ( G ) depending on the maximum degree of G. Furthermore, we study this parameter for trees, and also for the particular classes of paths and stars. Polynomial algorithms are designed for deciding whether a given list assignment admits an L ( d , s ) -list labeling on paths (for a given s unrestricted) and on trees (for s = 1 ).

Veröffentlichungszeitpunkt

  • Dezember 12, 2005