Publication details
Brooks-type theorem for the generalized list T-coloring
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/S0895480103437870 |
| Keywords | graph coloring; channel assignment problem; T-coloring; Brooks' theorem |
| Description | 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. |