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.