A Random Recolouring Method for Graphs and Hypergraphs
Colin McDiarmid · Cambridge University Press eBooks · 1997
We consider a simple randomised algorithm that seeks a weak 2-colouring of a hypergraph H ; that is, it tries to 2-colour the points of H so that no edge is monochromatic. If H has a particular well-behaved form of such a colouring, then the method is successful within expected number of iterations O ( n 3 ) when H has n points. In particular, when applied to a graph G with n nodes and chromatic number 3, the method yields a 2-colouring of the vertices such that no triangle is monochromatic in expected time O ( n 4 ). A hypergraph H on a set of points V is simply a collection of subsets E of V , the edges of H . A d-graph is a hypergraph in which each edge has size d . A weak 2- colouring of a hypergraph is a partition of the points into two ‘colour’ sets A and B such that each edge E meets both A and B . Deciding if a 3-graph has a weak 2-colouring is NP-complete. The following simple randomised recolouring method attempts to find a weak 2-colouring of a hypergraph H . It is assumed that we have a subroutine SEEK, which on input of a 2-colouring of the points outputs a monochromatic edge if there is one, and otherwise reports that there are none.