J 2005

Brooks-type theorem for the generalized list T-coloring

FIALA, J; Daniel KRÁĽ a R SKREKOVSKI

Základní údaje

Originální název

Brooks-type theorem for the generalized list T-coloring

Autoři

FIALA, J; Daniel KRÁĽ a R SKREKOVSKI

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2005, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.885

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

graph coloring; channel assignment problem; T-coloring; Brooks' theorem
Změněno: 6. 11. 2020 11:08, Mgr. Darina Boukalová

Anotace

V originále

We study the notion of a generalized list T-coloring which is a common generalization of the channel assignment problem and the T-coloring. An instance of the generalized list T-coloring is described by a triple (G, Lambda, t), where G is a graph, Lambda is a mapping which assigns the vertices of G lists of numbers (colors), and t is a mapping which assigns each edge of G a set of forbidden differences. We require that 0 is an element of t(e) for each edge e of G. The goal is to find a labeling c of the vertices of G with c(v) is an element of Lambda(v) for each vertex v, and | c( u) - c(v)| is not an element of t(uv) for each edge uv of G. An instance is balanced if the size of the list.( v) for each vertex v is equal to the sum of the sizes of t( e) for edges e incident with v. We state and prove a Brooks-type theorem for the generalized list T-coloring problem. This generalizes and unifies the previously known Brooks-type theorems for the channel assignment problem and for the T-coloring. The theorem characterizes balanced instances of the generalized list T-coloring with a good labeling. As a consequence, if G is a connected graph different from a Gallai tree, then all balanced instances on G have good labelings.