PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 2 | 315-327
Tytuł artykułu

The Incidence Chromatic Number of Toroidal Grids

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
33
Numer
2
Strony
315-327
Opis fizyczny
Daty
wydano
2013-05-01
online
2013-04-13
Twórcy
autor
  • Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence CNRS, LaBRI, UMR5800, F-33400 Talence, eric.sopena@labri.fr
autor
Bibliografia
  • [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]
  • [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] 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] 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] 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]
  • [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[Crossref]
  • [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]
  • [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] 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] 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]
  • [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] 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]
  • [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]
  • [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] 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1663
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.