PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 315-327
DOI: https://doi.org/10.7151/dmgt.1663

The Incidence Chromatic Number
of Toroidal Grids

Éric Sopena Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence CNRS, LaBRI, UMR5800, F-33400 Talence

Jiaojiao Wu Department of Applied Mathematics National Sun Yat-sen University, Taiwan

Abstract

An incidence in a graph G is a pair (v,e) with v ∈ V(G) and e ∈ E(G), such that v and e are incident. Two incidences (v,e) and (w,f) are adjacent if v = w, or e = f, or the edge vw equals e or f. The incidence chromatic number of G is the smallest k for which there exists a mapping from the set of incidences of G to a set of k colors that assigns distinct colors to adjacent incidences.

In this paper, we prove that the incidence chromatic number of the toroidal grid T_m,n = C_m^[¯] C_n equals 5 when m,n ≡ 0 (mod 5) and 6 otherwise.

Keywords: incidence coloring, Cartesian product of cycles, toroidal grid

2010 Mathematics Subject Classification: 05C15.

References

[1]	I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989) 11--22, doi: 10.1016/0012-365X(89)90073-3.
[2]	R.A. Brualdi and J.J. Quinn Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51--58, doi: 10.1016/0012-365X(93)90286-3.
[3]	P. Erdös and J. Nešetřil, Problem, In: Irregularities of Partitions, G. Halász and V.T. Sós (Eds.) (Springer, New-York) 162--163.
[4]	G. Fertin, E. Goddard and A. Raspaud, Acyclic and k-distance coloring of the grid, Inform. Proc. Lett. 87 (2003) 51--58, doi: 10.1016/S0020-0190(03)00232-1.
[5]	B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math. 163 (1997) 275--278, doi: 10.1016/0012-365X(95)00342-T.
[6]	M. Hosseini Dolama and E. Sopena, On the maximum average degree and the incidence chromatic number of a graph, Discrete Math. Theor. Comput. Sci. 7 (2005) 203--216.
[7]	M. Hosseini Dolama, E. Sopena and X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. 283 (2004) 121--128, doi: 10.1016/j.disc.2004.01.015.
[8]	C.I. Huang, Y.L. Wang and S.S. Chung, The incidence coloring numbers of meshes, Comput. Math. Appl. 48 (2004) 1643--1649, doi: 10.1016/j.camwa.2004.02.006.
[9]	D. Li and M. Liu, Incidence coloring of the squares of some graphs, Discrete Math. 308 (2008) 6569--6574, doi: 10.1016/j.disc.2007.11.047.
[10]	X. Li and J. Tu, NP-completeness of 4-incidence colorability of semi-cubic graphs, Discrete Math. 308 (2008) 1334--1340, doi: 10.1016/j.disc.2007.03.076.
[11]	M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005) 131--141, doi: 10.1016/j.disc.2005.02.003.
[12]	W.C. Shiu, P.C.B. Lam and D.L. Chen, On incidence coloring for some cubic graphs, Discrete Math. 252 (2002) 259--266, doi: 10.1016/S0012-365X(01)00457-5.
[13]	W.C. Shiu and P.K. Sun, Invalid proofs on incidence coloring, Discrete Math. 308 (2008) 6575--6580, doi: 10.1016/j.disc.2007.11.030.
[14]	E. Sopena and J. Wu , Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327--2333, doi: 10.1016/j.disc.2010.05.011.
[15]	S.D. Wang, D.L. Chen and S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 25 (2002) 397--405, doi: 10.1016/S0012-365X(01)00302-8.
[16]	J. Wu, Some results on the incidence coloring number of a graph, Discrete Math. 309 (2009) 3866--3870, doi: 10.1016/j.disc.2008.10.027.

Received 23 October 1011
Revised 20 February 2012
Accepted 7 March 2012