Nonrepetitive colorings of lexicographic product of graphs

Abstract : A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v1v2\textellipsisv2l for which c(vi)=c(vl+i) for all 1<=i<=l. Given graphs G and H with |V(H)|=k, the lexicographic product G[H] is the graph obtained by substituting every vertex of G by a copy of H, and every edge of G by a copy of Kk,k. We prove that for a sufficiently long path P, a nonrepetitive coloring of P[Kk] needs at least 3k+⌊k/2⌋ colors. If k>2 then we need exactly 2k+1 colors to nonrepetitively color P[Ek], where Ek is the empty graph on k vertices. If we further require that every copy of Ek be rainbow-colored and the path P is sufficiently long, then the smallest number of colors needed for P[Ek] is at least 3k+1 and at most 3k+⌈k/2⌉. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.97--110
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185617
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 17:13:58
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:08:57

Fichier

dmtcs-16-2-8.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185617, version 1

Collections

Citation

Balázs Keszegh, Balázs Patkós, Xuding Zhu. Nonrepetitive colorings of lexicographic product of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.97--110. 〈hal-01185617〉

Partager

Métriques

Consultations de la notice

87

Téléchargements de fichiers

85