Vertex colourings of edge-coloured graphs
Richard C. Brewster · Summit (Simon Fraser University) · 1993
tenivers*Ey which granted *he communiquer avec I'universite degree, qui a confbr6 le grade.Some pages may hawe indisencf La qualit6 d'impression de print esge~ially if the original certaines pages peut laisser B pages were typed wm& a poor desirer, surtout si les pages Vpewnger ribbon or if the originales ant et6 etniwersiv sent us an inferior dactylographiks B I'aide d'un phot06opy.ruban us6 ou si f'uuniversifii nous a fait parvenir une photocupie de -qualit6 infhrieure.preseat evidence suggesting that for edge-coloured graphs a structurd characterization that cornpfetel>-clafsifies %-hi& H-culslouring problems are SP-compf ete and which w e plynomid is ztdikely.This is similar to the case of directed graphs.fudeed, we establish a p~A~~0mia.lequivalence between the comptexity of H-coiouring for biipa.detwo-edge-cofotu~ed graphs and bipartite digraphs.W e show that the problem is pulpomid for paths m d that there exists trees, cn as few as 1'2 vertices, for which the problem is NP-complete.We study the problem for cycles and present an infinite f d y of NP-complete cycles with two edge colours; moreover, any cycle srnailer than the minimal element of the family is polynomial.We study the problem for cliques a d completely classify the complexity for all cliques on three or fewer vertices with two edge colours and for dI digon-free cliques on four vertices with two edge coburs.We show that a clique with Ii edge colours is NP-complete if it has more than zk vertices a d that there exists cfiqtres with k edge mlours and at most 2k vertices which are polynomid-We also establish an equiMfence between H-wlouring for edge-doweb graphs aab a new homomorphism problemthe Sabidussi Homomorphism Problem and thereby we are able to cl&@ the complexity for a large family of these problems.