Entire colouring

Материал из WikiGrapp

Entire colouring --- целая раскраска.

An entire colouring of a plane multigraph [math]\displaystyle{ G }[/math] is a map [math]\displaystyle{ \sigma: \; V \cup E \cup F \rightarrow S }[/math], where [math]\displaystyle{ S }[/math] is a set of colours, such that [math]\displaystyle{ \sigma(X) \neq \sigma(Y) }[/math] whenever [math]\displaystyle{ X,Y }[/math] are incident or adjacent elements, i.e. a pair of adjacent vertices, a vertex-edge pair with the edge incident on the vertex, an edge-face pair with the edge on a boundary of the face, etc.; a face touching either another face or an edge only in a vertex is not considered as adjacency.

The entire chromatic number, [math]\displaystyle{ \chi_{vef} }[/math], is the least size of [math]\displaystyle{ S }[/math] admitting such a coloring. For example, if [math]\displaystyle{ G }[/math] consists of two copies of [math]\displaystyle{ K_{3} }[/math] joined in a single common vertex, then [math]\displaystyle{ \chi_{vef}(G) = 6 }[/math]. The entire choice number, [math]\displaystyle{ \hat{\chi}_{vef} }[/math], is the least integer [math]\displaystyle{ k }[/math] such that if [math]\displaystyle{ L(A) }[/math] is a set (list) of size [math]\displaystyle{ k }[/math] for each [math]\displaystyle{ A \in V \cup E \cup F }[/math], then there exists an entire colouring [math]\displaystyle{ \sigma }[/math] of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ \sigma(A) \in L(A) }[/math] for each such [math]\displaystyle{ A }[/math].