k-tuple chromatic number of the cartesian product of graphs

A k-tuple coloring of a graph G assigns a set of k colors to each vertex of G such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The k-tuple chromatic number of G, χk(G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known t...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Koch, Ivo
Publicado: 2015
Materias:
Cartesian product of graphs
Cayley graphs
Hom-idempotent graphs
k-tuple colorings
Kneser graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p243_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p243_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v50_n_p243_Bonomo
record_format dspace
spelling paper:paper_15710653_v50_n_p243_Bonomo2025-07-30T19:00:07Z k-tuple chromatic number of the cartesian product of graphs Bonomo, Flavia Koch, Ivo Cartesian product of graphs Cayley graphs Hom-idempotent graphs k-tuple colorings Kneser graphs A k-tuple coloring of a graph G assigns a set of k colors to each vertex of G such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The k-tuple chromatic number of G, χk(G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known that χ(G□H)=max{χ(G), χ(H)}. In this paper, we show that there exist graphs G and H such that χk(G□H)>max{χk(G), χk(H)} for k≥2. Moreover, we also show that there exist graph families such that, for any k≥1, the k-tuple chromatic number of their cartesian product is equal to the maximum k-tuple chromatic number of its factors. © 2015 Elsevier B.V. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Koch, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p243_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p243_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Cartesian product of graphs
Cayley graphs
Hom-idempotent graphs
k-tuple colorings
Kneser graphs
spellingShingle Cartesian product of graphs
Cayley graphs
Hom-idempotent graphs
k-tuple colorings
Kneser graphs
Bonomo, Flavia
Koch, Ivo
k-tuple chromatic number of the cartesian product of graphs
topic_facet Cartesian product of graphs
Cayley graphs
Hom-idempotent graphs
k-tuple colorings
Kneser graphs
description A k-tuple coloring of a graph G assigns a set of k colors to each vertex of G such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The k-tuple chromatic number of G, χk(G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known that χ(G□H)=max{χ(G), χ(H)}. In this paper, we show that there exist graphs G and H such that χk(G□H)>max{χk(G), χk(H)} for k≥2. Moreover, we also show that there exist graph families such that, for any k≥1, the k-tuple chromatic number of their cartesian product is equal to the maximum k-tuple chromatic number of its factors. © 2015 Elsevier B.V.
author Bonomo, Flavia
Koch, Ivo
author_facet Bonomo, Flavia
Koch, Ivo
author_sort Bonomo, Flavia
title k-tuple chromatic number of the cartesian product of graphs
title_short k-tuple chromatic number of the cartesian product of graphs
title_full k-tuple chromatic number of the cartesian product of graphs
title_fullStr k-tuple chromatic number of the cartesian product of graphs
title_full_unstemmed k-tuple chromatic number of the cartesian product of graphs
title_sort k-tuple chromatic number of the cartesian product of graphs
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p243_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p243_Bonomo
work_keys_str_mv AT bonomoflavia ktuplechromaticnumberofthecartesianproductofgraphs
AT kochivo ktuplechromaticnumberofthecartesianproductofgraphs
_version_ 1840323172916789248

Ejemplares similares