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

KOCH, IVO; DURÁN, GUILLERMO; BONOMO, FLAVIA; VALENCIA-PABON, MARIO

ARS COMBINATORIA

CHARLES BABBAGE RES CTR

Lugar: WINNIPEG; Año: 2018 vol. 137 p. 317 - 333

0381-7032

In the (k,i)-coloring problem, we aim to assign sets of colors of size k to the vertices of a graph G, 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 k-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.