----　　 A generalization of coloring problem of graph.　　 ----

　　1.Definition　　　　　　　　　　　　　　　　

　　The ordinary coloring problem is defined as follows.

　　Place different colors on two vertices which are next each other on a planar graph.

　　Place different colors on two vertices which are "near" each other on a planar graph.

　　For different two vertices a and b,　either condition 1. or 2. is filled.

　　c.2. There are three paths of length 2 between a and b.

　　c.1 and c.2 is represented as (1,1) and (2,3) respectively.

　　if edges are added between all pairs of vertices which satisfy (2,3)　on G,

　　　　 where chr(x) means the chromatic number of x.

　　Consider about the following graph which has 7 vertices.

　　　　　　 a　　　　 b　　　　c　　　　　　 the names of vertices

　　This is a graph of polyhedron which has 10 triangles.

　　For example, between a and c, there are 3 paths abc,axc,ayc.

　　To prove that 8 colors are enough is as easy as 5 colors theorem of plane. And to prove that 7 colors are enough is interesting but it doesn't have difficulty such as 4 colors theorem.　　　　

　　T.12c　　12 colors are necessary for torus graphs.

　　The graph which is defined as follows needs 12 colors.

　　V={a(1),a(2),a(3),a(4),a(5),a(6),b(1),b(2),b(3),b(4),b(5),b(6)}

　　E={a(i)a(j), i-j=5 mod 6, b(k)b(l), k-l=5 mod 6, a(m)b(n), n-m=1 or 2 or 4 or 5 mod 6}

　　　　　　　　　　　　　　 upside　　　　　　　　　　　　　　 underside

　　　　　　　　　　 a6　　　　a1　　　　a2　　　　　　 a2　　　　 a1　　　　 a6

　　　　　　　　　　　　 b6　　b1　　b2　　　　　　　　　　　b2　　b1　　b6

　　　　　　　　　　　　 b5　　b4　　b3　　　　　　　　　　　b3　　b4　　b5

　　　　　　　　　　 a5　　　　a4　　　　a3　　　　　　a3　　　　 a4　　　　 a5

　　For example between a(1) and a(3), there are 3 paths a(1)a(2)a(3), a(1)b(2)a(3), a(1)b(5)a(3).

　　　　 Where G is a graph on a sphere, H is a graph on a torus.

　　　　 The case of graph Near_{2,k}(H), these numbers are lower bound of the chromatic number.

　　　　 And "-" means that for any number N, a graph which needs N colors exists

　　See the section 5 and 6 which is the explanation of this table.

　　The characterization of the graphs Near_{2,k}(G) or Near_{2,k}(H) are also interesting problems.

　　K(8) doesn't exist on Near_{2,3}(G), because T.7C says 7 colors are enough.

　　Besides them many problems are possible, but who will solve chr(Near_{50,500}(G))?

　　[The chromatic number of (2,n)-edge added planar graphs.]

　　The class of (2,n)-edge added planar graph is defined as follows:

　　G(2,n)={ x : Exist y (x is the (2,n)-edge added graph of y) and (y is a planar graph) }

　　where (2,n)-edge added graph is defined as follows:

　　If between two vertice a,b on graph y, there are n paths of length 2, then the edge ab is named (2,n)-edge on y. And if we add all these (2,n)-edges to y, the graph is called　(2,n)-edge added graph of y. If a (2,n)-edge exists already in y, it is not necessary to add it.

　　chr(Near_{2,n}(G)) gives the chromatic number of (2,n)-edge added planar graphs.

　　chr(Near_{2,n}(G))=" Maximal of chr(x) : x is a member of G(2,n) "

　　　　　　　　 fig.1　　　　　　　　　　　　　　　　　　　　　　　　 fig.2

　　　　　　　　 a graph h　　　　　　　　　　　　　　　　　　　　 the (2,3)-edge added graph of h

　　　　　　　　there are 3 paths of length 2 between a and b, so edge ab is a (2,3)-edge.

　　　　　　　　 fig.3　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 fig.4　　

a graph i　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　the (2,3)-edge added graph of i

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 =K(5)

　　The sufficiency of these chromatic number have been proved.

　　n=3　　　　　　　　　　　　　　　　fig.5　　　　　　

　　(2,3)-edge added graph of G7 is K(7), it needs 7 colors. chr(K(7))=7.

　　　　　　　　　　　　　　A plain graph G6

　　(2,4)-edge added graph of G6 is K(6), it needs 6 colors. So,chr(Near_{2,4}(G))=6.

n=5　　　　　　　　　　　　　　　　　　fig.7

　　　　　　　　　　　　　　　　　　A plain graph G7

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　fig.8

　　　　　　　　　　　　　　　　　　　　　　 (2,5)-edge added graph of G7

　　The center pentagon needs 3 colors for coloring, and the color of vertex x must be different

to these 3 colors, and the color of vertex y is also different to them. Still, the color of x

and the color of y are different, because a edge E exists.

　　After all, the chromatic number of this graph is 5. So, chr(Near_{2,5}(G))=5.

　　[The chromatic number of (2,n)-edge added torus graphs]

　　In this section, chr(Near_{2,n}(H)) gives only a lower bound of the chromatic number of (2,n)-edge added torus graphs.

　　chr(Near_{2,n}(H))=" Maximal of chr(x) : x is a known member of H(2,n) "

　　where H(2,n) means the set of (2,n)-edge added torus graphs.

　　　　n=3　　　　　　　　　　　　　　　　fig.9　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 fig.10　　　　

　　　　　　　　a view from upper side of a torus graph G12　　　　a view from down side of G12

　　　　All of the pairs of vertices on this graph are next each other or three paths of length two exist between them, so (2,3)-edge added graph of the graph is K(12).

　　　　It means a lower bound of chr(Near_{2,3}(H))=12

　　　　The case of n=4 is a similar graph as the above graph whose vertices are 10.

　　　　The case of n=6, the graph of triangle lattice on a torus with period 3, which has 9 vertices, gives K(9) as the (2,6)-edge added graph.

　　　　The case of n=7, the K(7) on a torus which is well known needs 7 colors.

　　7. Sumary of the proof of the sufficiency in T.7.C.

　　The definition is based on D.1. The numbers of figures are local.

　　If an outside-diagonal edge such that A in fig.1 exists on a pentagon with a star, then a pair of vertices which are not near each other exists on the pentagon.

　　We asume all the pair of vertices on the pentagon are near.

　　If b,e is (1,1) then an edge be exists, but a cycle acfa sepalates b and e, so it is impossible.

　　It means b,e is (2,3). So three edges of two length must exist between b and e, the edges bae and bfe already exist, then one more edge bce is needed. Hence an out-side diagonal edge B exists.　　　　　　　　　　 (fig.2)

　　No edge bd exists, so it is impossible that b,d is (1,1).

　　For (2,3), bfd and bcd already exist, so the edge ad is needed, but a cycle efce sepalates a and d, so it is also impossible. It means a pair of a and d is not near.

　　7 colors are enough for coloring　any planar graph.

　　It is well known that if　a planar graph is trianglated then a vertex whose degree is less than five must exist.

　　1.An outside-diagonal edge exists on the pentagon around the vertex.

　　2.No outside-diagonal edge exists on the pentagon, and a pair of vertices on the pentagon are not near each other.

　　3.No outside-diagonal edge exists on the pentagon, and all pair of vertices on the pentagon are near each other.

　　One pair of vertices which are not naer each other exists.

　　Because, the condition 1 and Theorem 1 leads to the fact that such a pair exists

　　Then it is possible to make　a planar graph G(n) which contains a graph drawed in fig.3 to be　a planar graph G(n-1) as follows.

　　　　 step.1.　　Put f and fa, fb, fc, fd, fe off.　　(fig,4,)

　　　　 step.2　　Make b and e be a same vertex.　　(fig.5)

　　　　 step.3.　　ab and ae becomes a double edge, so put one edge off

　　　　 Take reverce steps 3 to 1, then G(n) becomes to contain fig.3.

　　　　 b and e are colored with a same color, it is allowed because they are not near.

　　　　 Each a, b, c, d, e and f are (1,1) and two vetices are (2,3), so f must be colored with a different color from these 7 vertices.

　　　　 They are colored with 6 colors, notice color of b and e is same, so we are able to put 7th color on f.

　　If a and c are (1,1) then an outside-diagonal edge ac must exist. It contradicts to the condition of case 3. (fig.6)

　　So, a and c are (2,3). There are already two paths abc, afc, so one more path is needed.

　　If an edge ad exists then a path adc is length of two but ad is an ouside-diagonaal edge so it is impossible.

　　It means, a path agc exists out of the pentagon.　　　　　　 (fig.7)

　　b exists in a cycle agcf so an edge be doesn't exist. It means b and e are not (1,1).

　　b and e are (2,3). For this proposition, bae and bfe exist, and if an edge ce exists then bce is a path of length two, but it is outside-diagonal.

　　So, two edges bg and ge exist. bge is a path of length two. Three paths of length two become to exist. It satisfies (2,3).　　(fig.8)

　　If we consider about b and d, in the same way with the case of b and e, we obtain a result that edges bg and gd exist. (fig.9)

　　The cases of a and d, and c and e, the propositions that they are near is already satisfied. No other edge is needed.

　　In this case, a, b, c, d, e are (1, 1) to f and g is (2, 3) to f.

　　If one more vertex h which is (2, 3 ) to f exists, then beside gef, gdf, another path of length two must exist, but a, b, c are in a cycle egde, so it is impossible.

　　It means only 6 vertices are near to the vertex f in the case 3. (fig.10)

　　Then it is possible to make a plainer graph G(n) which contains a graph drawed in fig.9 to be a plainer graph G(n-1) as follows.

　　　　 step.1.　　Put f and fa, fb, fc, fd, fe off.　　(fig,11,)

　　　　 step.2.　　Put eb between e and b, put ec between e and c.　　(fig.12)

　　　　 Take reverce steps 2 to 1, then G(n) becomes to contain fig.9.

　　　　 Each a, b, c, d, e and f are (1,1) and one vetex g is (2,3), so f must be colored with a different color from these 6 vertices.

　　　　 They are colored with 6 colors, so we are able to put 7th color on f.