6533b825fe1ef96bd1282566

RESEARCH PRODUCT

Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs

Jean-luc Baril Hamamache Kheddouci Olivier Togni

subject

[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]total coloringadjacent vertex-distinguishingvertex-distinguishingComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISIONedge-coloring[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]graphgraph productsAMS 05C15[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]total adjacent vertex-distinguishingMathematicsofComputing_DISCRETEMATHEMATICS

description

International audience; This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.

yearjournalcountryeditionlanguage
2012-10-01
https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00762728