On the (k, i)-coloring of cacti and complete graphs

In the (k, i)-coloring problem, we aim to assign sets of colors of size k to the vertices of a graph C, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called the (k, i)-chro...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, F., Durán, G., Koch, I., Valencia-Pabon, M.
Formato:	JOUR
Materias:	(k Cactus Complete graphs Generalized fc-tuple coloring I)-coloring
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_03817032_v137_n_p317_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_03817032_v137_n_p317_Bonomo
record_format	dspace
spelling	todo:paper_03817032_v137_n_p317_Bonomo2023-10-03T15:33:42Z On the (k, i)-coloring of cacti and complete graphs Bonomo, F. Durán, G. Koch, I. Valencia-Pabon, M. (k Cactus Complete graphs Generalized fc-tuple coloring I)-coloring In the (k, i)-coloring problem, we aim to assign sets of colors of size k to the vertices of a graph C, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called the (k, i)-chromatic number. We present in this work a very simple linear time algorithm to compute an optimum (k, i)- coloring of cycles and we generalize the result in order to derive a polynomial time algorithm for this problem on cacti. We also perform a slight modification to the algorithm in order to obtain a simpler algorithm for the close coloring problem addressed in [R.C. Brigham and R.D. Dutton, Generalized fc-tuple colorings of cycles and other graphs, J. Combin. Theory B 32:90-94, 1982], Finally, we present a relation between the (k,i)-coloring problem on complete graphs and weighted binary codes. © 2018 Charles Babbage Research Centre. All rights reserved. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03817032_v137_n_p317_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	(k Cactus Complete graphs Generalized fc-tuple coloring I)-coloring
spellingShingle	(k Cactus Complete graphs Generalized fc-tuple coloring I)-coloring Bonomo, F. Durán, G. Koch, I. Valencia-Pabon, M. On the (k, i)-coloring of cacti and complete graphs
topic_facet	(k Cactus Complete graphs Generalized fc-tuple coloring I)-coloring
description	In the (k, i)-coloring problem, we aim to assign sets of colors of size k to the vertices of a graph C, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called the (k, i)-chromatic number. We present in this work a very simple linear time algorithm to compute an optimum (k, i)- coloring of cycles and we generalize the result in order to derive a polynomial time algorithm for this problem on cacti. We also perform a slight modification to the algorithm in order to obtain a simpler algorithm for the close coloring problem addressed in [R.C. Brigham and R.D. Dutton, Generalized fc-tuple colorings of cycles and other graphs, J. Combin. Theory B 32:90-94, 1982], Finally, we present a relation between the (k,i)-coloring problem on complete graphs and weighted binary codes. © 2018 Charles Babbage Research Centre. All rights reserved.
format	JOUR
author	Bonomo, F. Durán, G. Koch, I. Valencia-Pabon, M.
author_facet	Bonomo, F. Durán, G. Koch, I. Valencia-Pabon, M.
author_sort	Bonomo, F.
title	On the (k, i)-coloring of cacti and complete graphs
title_short	On the (k, i)-coloring of cacti and complete graphs
title_full	On the (k, i)-coloring of cacti and complete graphs
title_fullStr	On the (k, i)-coloring of cacti and complete graphs
title_full_unstemmed	On the (k, i)-coloring of cacti and complete graphs
title_sort	on the (k, i)-coloring of cacti and complete graphs
url	http://hdl.handle.net/20.500.12110/paper_03817032_v137_n_p317_Bonomo
work_keys_str_mv	AT bonomof onthekicoloringofcactiandcompletegraphs AT durang onthekicoloringofcactiandcompletegraphs AT kochi onthekicoloringofcactiandcompletegraphs AT valenciapabonm onthekicoloringofcactiandcompletegraphs
_version_	1807314839632084992

On the (k, i)-coloring of cacti and complete graphs

Ejemplares similares