Subject: coloring the polyhedral tori
Date: Oct 30 1998 at 15:41 CST (timestamp)
From: Rusin
To: test out claims about chromatic numbers of nonplanar graphs :-)

We have models of 1-holed tori with minimal vertices; 
are these difficult to color?

#Faces as sets of vertices:
F1:= [ 1, 2, 3 ]:
F2:= [ 2, 1, 4 ]:
F3:= [ 3, 5, 1 ]:
F4:= [ 4, 6, 2 ]:
F5:= [ 6, 1, 5 ]:
F6:= [ 5, 2, 6 ]:
F7:= [ 3, 4, 5 ]:
F8:= [ 4, 3, 6 ]:
F9:= [ 7, 1, 6 ]:
F10:= [ 7, 2, 5]:
F11:= [ 1, 7, 4]:
F12:= [ 2, 7, 3]:
F13:= [ 3, 7, 6]:
F14:= [ 4, 7, 5]:

#Edges as sets of faces
for i from 1 to 6 do for j from i+1 to 7 do E.i.j:=[]:
	for k from 1 to 14 do if member(i,F.k) and member(j,F.k) then
		E.i.j:=[op(E.i.j), k]:fi: od:
	od:od:

#Neighbors as sets of faces
for i to 14 do N.i:=[]:
	for j to 14 do if i<>j and nops({op(F.i)} intersect {op(F.j)})>1 then N.i:=[op(N.i),j]:fi:od:
	od:


N1   [2, 3, 12]
N2   [1, 4, 11]
N3   [1, 5, 7]
N4   [2, 6, 8]
N5   [3, 6, 9]
N6   [4, 5, 10]
N7   [3, 8, 14]
N8   [4, 7, 13]
N9   [5, 11, 13]
N10   [6, 12, 14]
N11   [2, 9, 14]
N12   [1, 10, 13]
N13   [8, 9, 12]
N14   [7, 10, 11]

Neighbor diagram:

         *      (6)
         |       |
         |       |
        13      10
       /  \    /  \
      /    \  /    \
     9      12      14
     |       |       |
     |       |       |
    11       1       7
   /  \     / \     / \
  /    \   /   \   /   \
(14)     2       3      *         (*) = face #8
         |       |
         |       |
         4       5
       /  \    /  \
      /    \  /    \
     *       6     (9)
    
    
Note the pattern: 1 in center (8 opposite); 2,3,12 in one ring, 
4,5   7,10  13,11  in next,  6 (9) * 14 (6) * 9 (14) *  in last
Thus the thing is 2-colorable:
Red:  1,4,5,7,10,13,11
Blue: 2,3,12,6,9,14,8