Artículo
Bonomo, F.; Durán, G.; Koch, I.; Valencia-Pabon, M. "On the (k, i)-coloring of cacti and complete graphs" (2018) Ars Combinatoria. 137:317-333
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | On the (k, i)-coloring of cacti and complete graphs |
| Autor: | Bonomo, F.; Durán, G.; Koch, I.; Valencia-Pabon, M. |
| Filiación: | Dep. de Computatión, CONICET, Universidad de Buenos, Aires, Argentina Dep. de Matematica, Instituto de Cálculo, CONICET, Universidad de Buenos Aires, Argentina Dep. de Ingeniería Industrial, Universidaw de Chile, Santiago, Chile Instituto de Ciencias, Universidad National de General Sarmiento, Argentina CNRS, Université Paris-13, Villetaneuse, France |
| Palabras clave: | (k; Cactus; Complete graphs; Generalized fc-tuple coloring; I)-coloring |
| Año: | 2018 |
| Volumen: | 137 |
| Página de inicio: | 317 |
| Página de fin: | 333 |
| Título revista: | Ars Combinatoria |
| Título revista abreviado: | Ars Comb. |
| ISSN: | 03817032 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo |
Referencias:
- Agreli, E., Vardy, A., Zeger, K., Upper bounds for constant-weight codes (2000) IEEE Transactions on Information Theory, 46 (7), pp. 2373-2395
- Berge, C., (1976) Graphs and Hypergraphs, , North-Holland, Amsterdam
- Bollobas, B., Thomason, A., Set colourings of graphs (1979) Discrete Mathematics, 25 (1), pp. 21-26
- Brigham, R.C., Dutton, R.D., Generalized A;-tuple colorings of cycles and other graphs (1982) Journal of Combinatorial Theory. Series B, 32, pp. 90-94
- Denley, T., The odd girth of the generalized Kneser graph (1997) European Journal of Combinatorics, 18 (6), pp. 607-611
- Friedmann, C., Markenzon, L., Waga, C., Total coloring of block- cactus graphs (2009) Journal of Combinatorial Mathematics and Combinatorial Computing, 78, pp. 273-283
- Godsil, C.D., Royle, G., (2001) Algebraic Graph Theory, , Graduate Texts in Mathematics. Springer
- Graham, R.L., Sloane, N.J.A., Lower bounds for constant weight codes (1980) IEEE Transactions on Information Theory, 26, pp. 37-43
- Hanani, H., On quadruple systems (1960) Canadian Journal of Mathematics, 12, pp. 145-157
- Hanani, H., The existence and construction of balanced incomplete block designs (1961) Annals of Mathematical Statistics, 32, pp. 361-386
- Hanani, H., On some tactical configurations (1963) Canadian Journal of Mathematics, 15, pp. 702-722
- Hanani, H., A balanced incomplete block design (1965) Annals of Mathematical Statistics, 36, p. 711
- Hilton, A., Rado, R., Scott, S., A (< 5)-colour theorem for planar graphs (1973) Bulletin of the London Mathematical Society, 5, pp. 302-306
- Johnson, S.M., A new upper bound for error-correcting codes (1962) IEEE Transactions on Information Theory, 8, pp. 203-207
- Khan, N., Pal, M., Adjacent vertex distinguishing edge colouring of cactus graphs (2013) International Journal of Engineering and Innovative Technology, 4, pp. 62-71
- Khan, N., Pal, A., Pal, M., Edge colouring of cactus graphs (2009) Advanced Modeling and Optimization, 4, pp. 407-421
- Mendez-Di'Az, I., Zabala, P., A generalization of the graph coloring problem (1999) Investigacion Operativa, 8, pp. 167-184
- Mendez-Di'Az, I., Zabala, P., Solving a multicoloring problem with overlaps using integer programming (2010) Discrete Applied Mathematics, 158, pp. 349-354
- Stahl, S., N-Tuple colorings and associated graphs (1976) Journal of Combinatorial Theory. Series B, 20, pp. 185-203
Citas:
---------- APA ----------
Bonomo, F., Durán, G., Koch, I. & Valencia-Pabon, M. (2018) . On the (k, i)-coloring of cacti and complete graphs. Ars Combinatoria, 137, 317-333.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., Durán, G., Koch, I., Valencia-Pabon, M. "On the (k, i)-coloring of cacti and complete graphs" . Ars Combinatoria 137 (2018) : 317-333.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo [ ]
---------- MLA ----------
Bonomo, F., Durán, G., Koch, I., Valencia-Pabon, M. "On the (k, i)-coloring of cacti and complete graphs" . Ars Combinatoria, vol. 137, 2018, pp. 317-333.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Koch, I., Valencia-Pabon, M. On the (k, i)-coloring of cacti and complete graphs. Ars Comb. 2018;137:317-333.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v137_n_p317_Bonomo [ ]
