graph coloring

(redirected from Vertex colouring)

graph coloring

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
If an edge k-weighting gives rise to such a proper vertex colouring, we say that the weighting is a vertex colouring by sums.
One may also obtain a vertex colouring from an edge k-weighting by considering the products, sets, or multisets of incident edge weights.
The following conjecture motivates the study of total weightings and vertex colouring by sums:
Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-list-weighting which is a vertex colouring by sums is denoted [ch.sup.e.sub.[summation]](G); each of the parameters above generalizes similarly.
A vertex colouring by sequences, c, is prefix distinguishing if, for any uv [member of] E(G) with [greater than or equal to] d(v) [greater than or equal to] 2, c(v) is not the prefix of c(u); in other words, if c(v) = [a.sub.1][a.sub.2] ...
An S-edge-weighting gives a vertex colouring if the weighted degrees of adjacent vertices are different.
Thus if one choice of a and b gives a vertex colouring, then any other choice of a and b will as well.
Assigning w([e.sub.2]) = a and w([e.sub.4]) = b does not yield a proper vertex colouring of G if and only if either w([v.sub.0]) = 2a or w([v.sub.5]) = a + b.
This weighting gives a proper vertex colouring. Assume [n.sub.3] [greater than or equal to] 1.
Each of these edge-weightings gives a proper vertex colouring.
The k-total-weighting is neighbour-distinguishing (or vertex colouring, see (1)) if for every edge uv, w(u) + [[SIGMA].sub.e[contains as member]u] w(e) [not equal to] w(v) + [[SIGMA].sub.e[contains as member]v] w(e).
Informally speaking, a track layout of a graph consists of a proper vertex colouring, and a total order of each colour class, such that between each pair of colour classes, no two edges cross (with respect to the orders of the colour classes that contain the endpoints of the edges).