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...
| Publicado: |
2018
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v137_n_p317_Bonomo |
| Aporte de: |
| id |
paper:paper_03817032_v137_n_p317_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_03817032_v137_n_p317_Bonomo2023-06-08T15:40:49Z On the (k, i)-coloring of cacti and complete graphs (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. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo 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 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. |
| 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 |
| publishDate |
2018 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v137_n_p317_Bonomo |
| _version_ |
1768541941025210368 |