The Incidence Chromatic Number of Toroidal Grids

Éric Sopena; Jiaojiao Wu

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 315-327
  • ISSN: 2083-5892

Abstract

top
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 Tm,n = Cm2Cn equals 5 when m, n ≡ 0(mod 5) and 6 otherwise.

How to cite

top

Éric Sopena, and Jiaojiao Wu. "The Incidence Chromatic Number of Toroidal Grids." Discussiones Mathematicae Graph Theory 33.2 (2013): 315-327. <http://eudml.org/doc/268177>.

@article{ÉricSopena2013,
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 Tm,n = Cm2Cn equals 5 when m, n ≡ 0(mod 5) and 6 otherwise.},
author = {Éric Sopena, Jiaojiao Wu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {incidence coloring; Cartesian product of cycles; toroidal grid; Cartesian product},
language = {eng},
number = {2},
pages = {315-327},
title = {The Incidence Chromatic Number of Toroidal Grids},
url = {http://eudml.org/doc/268177},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Éric Sopena
AU - Jiaojiao Wu
TI - The Incidence Chromatic Number of Toroidal Grids
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 315
EP - 327
AB - 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 Tm,n = Cm2Cn equals 5 when m, n ≡ 0(mod 5) and 6 otherwise.
LA - eng
KW - incidence coloring; Cartesian product of cycles; toroidal grid; Cartesian product
UR - http://eudml.org/doc/268177
ER -

References

top
  1. [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[Crossref] Zbl0684.05033
  2. [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[Crossref] 
  3. [3] P. Erdős and J. Nešetřil, Problem, In: Irregularities of Partitions, G. Hal´asz and V.T. S´os (Eds.) (Springer, New-York) 162-163. 
  4. [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[Crossref] 
  5. [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[Crossref] Zbl0871.05022
  6. [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. Zbl1153.05318
  7. [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[Crossref] Zbl1064.05057
  8. [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[Crossref] Zbl1062.05059
  9. [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[Crossref][WoS] 
  10. [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[WoS] 
  11. [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[Crossref] Zbl1059.05051
  12. [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[Crossref] 
  13. [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[Crossref][WoS] Zbl1191.05045
  14. [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[Crossref][WoS] Zbl1213.05101
  15. [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[Crossref] 
  16. [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[Crossref][WoS] Zbl1250.05051

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.