On Colouring the Nodes of a Network
R. L. Brooks · Birkhäuser Boston eBooks · 2009
Let N be a network (or linear graph) such that at each node not more than n lines meet (where n > 2), and no line has both ends at the same node. Suppose also that no connected component of N is an n-simplex. Then it is possible to colour the nodes of N with n colours so that no two nodes of the same colour are joined.