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, F., Koch, I., Torres, P., Valencia-Pabon, M.
Formato: JOUR
Materias:
Cartesian product of graphs
Cayley graphs
Hom-idempotent graphs
k-tuple colorings
Kneser graphs
Acceso en línea: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 todo:paper_15710653_v50_n_p243_Bonomo
record_format dspace
spelling todo:paper_15710653_v50_n_p243_Bonomo2023-10-03T16:27:08Z k-tuple chromatic number of the cartesian product of graphs Bonomo, F. Koch, I. Torres, P. Valencia-Pabon, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F.
Koch, I.
Torres, P.
Valencia-Pabon, M.
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.
format JOUR
author Bonomo, F.
Koch, I.
Torres, P.
Valencia-Pabon, M.
author_facet Bonomo, F.
Koch, I.
Torres, P.
Valencia-Pabon, M.
author_sort Bonomo, F.
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
url http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p243_Bonomo
work_keys_str_mv AT bonomof ktuplechromaticnumberofthecartesianproductofgraphs
AT kochi ktuplechromaticnumberofthecartesianproductofgraphs
AT torresp ktuplechromaticnumberofthecartesianproductofgraphs
AT valenciapabonm ktuplechromaticnumberofthecartesianproductofgraphs
_version_ 1807316508649455616

Ejemplares similares