Generalized Acyclic Coloring Of Planar Grid

Acyclic coloring is a graph G does not contain2-normal color circle. Generalized r-acyclic coloring is a normal coloring of neighboring points in different colors, and each circle at least contains min{|C|,r}, r≥3colors, the smallest number for coloring is αr (G).Thesis mainly studies the Generalized r-acyclic coloring of infinite planar triangular mesh, mesh, hexagonal grid, the special sub-graph of triangular named the mosaic of different torsion square and the special sub-graph of mesh named the mosaic of cut angle square. On the basis of analyzing the structure of the grid, through establishing a cartesian grid rectangular coordinate system, the method of construct coloring and the proof by contradiction have been used, and finally determined the number of generalized r-acyclic coloring, got some precise value, as well as part of the boundary value. Specific results are as follows:(1) To the infinite planar triangular mesh Tr, this paper obtained that the precise value of general3-acyclic coloring is4, the generalized4-acyclic coloring number got up and low bounds. Respectively, the up bound is6and the low bound is5.(2) To the infinite planar mesh L2, this paper obtained that the precise value of general3-acyclic coloring is3, the precise value of general4-acyclic coloring is5.(3) To the infinite planar hexagonal grid H, this paper obtained that the precise value of general3-acyclic coloring is3, the precise value of general4-acyclic coloring is4.(4) To the mosaic of different twist ridge square T1, this paper obtained that the precise value of general3-acyclic coloring is4.(5) To the mosaic of cutting angle square T2, that the precise value of general3-acyclic coloring is3, the precise value of general4-acyclic coloring is4.