EMCSR'96 Plenary Lecture

Wednesday, April 10, 1996, 9:00 am
University of Vienna, Lecture Room 47


Uncolourable Trivalent Graphs

A 3-graph is said to be uncolourable if its links cannot be completely coloured with just three colours so that similarly-coloured links do not meet at any node. It is considered trivial if it is less than five- connected, or if it can obviously be factored so that one of the factors is a smaller nontrivial uncolourable graph. Isaacs (Am Math Monthly, 73 (1975) 221-239) described an infinite class of nontrivial uncolourable 3-graphs but was unable to answer the question whether it accounts for all such graphs. The present communication demonstrates a method of factorization that supplies an affirmative answer to this question.