List total coloring

List total coloring --- предписанная тотальная раскраска.

Suppose that a set [math]\displaystyle{ L(x) }[/math] of colors, called a list of [math]\displaystyle{ x }[/math], is assigned to each element [math]\displaystyle{ x \in V(G) \cup E(G) }[/math]. Then a total coloring [math]\displaystyle{ \varphi }[/math] of [math]\displaystyle{ G }[/math] is called a list total coloring of [math]\displaystyle{ G }[/math] for [math]\displaystyle{ L }[/math] if [math]\displaystyle{ \varphi(x) \in L(x) }[/math] for each element [math]\displaystyle{ x \in V(G) \cup E(G) }[/math], where [math]\displaystyle{ \varphi(x) }[/math] is the color assigned to [math]\displaystyle{ x }[/math] by [math]\displaystyle{ \varphi }[/math]. The list total coloring [math]\displaystyle{ \varphi }[/math] is simply called an [math]\displaystyle{ L }[/math]-total coloring. An ordinary total coloring is an [math]\displaystyle{ L }[/math]-total coloring for which all lists [math]\displaystyle{ L(x) }[/math] are same. Thus an [math]\displaystyle{ L }[/math]-total coloring is a generalization of a total coloring. The list total coloring problem asks whether a graph [math]\displaystyle{ G }[/math] has an [math]\displaystyle{ L }[/math]-total coloring for given [math]\displaystyle{ G }[/math] and [math]\displaystyle{ L }[/math]. The problem is NP-complete in general, because the ordinary total coloring problem is NP-complete. The list vertex-coloring problem and list edge-coloring problem are similarly defined. The list vertex-coloring problem can be solved in polynomial time for partial [math]\displaystyle{ k }[/math]-trees and hence for series-parallel graphs.