By Fred Holroyd
The Open University
Abstract:
A semi-total colouring of a graph G allocates colours to the edges and vertices so that adjacent edges have distinct colours and each vertex has a different colour from its incident edges (but adjacent vertices may have the same colour). The beta parameter, b(G), is the minimum number of pairs of same-coloured vertices in any semi-total colouring of G using D+1 colors (where D is the maximum degree). In general b(G) can be quite large: However it is conjectured that it is at most 2 if G is a critical graph (for total chromatic number).
An upper bound, log-linear in D, is derived for b(G).
Thursday, February 17, 2005
At 3:30 in Wallace 430