TY - JOUR
N2 - A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer k for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by x=( G). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G◦ lH is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most x=( G◦ lH) + 1 colors in the remaining cases.
L1 - http://sd.czasopisma.pan.pl/Content/130799/art10_int.pdf
L2 - http://sd.czasopisma.pan.pl/Content/130799
PY - 2024
IS - No 1
EP - 223
DO - 10.24425/acs.2024.149658
KW - corona graph
KW - 𝑙-corona products
KW - cubic graph
KW - equitable chromatic number
KW - polynomial algorithm
KW - 1-absolute approximation algorithm
A1 - Furmańczyk, Hanna
A1 - Kubale, Marek
PB - Committee of Automatic Control and Robotics PAS
VL - vol. 34
DA - 29.03.2024
T1 - Equitable colorings of l-corona products of cubic graphs
SP - 211
UR - http://sd.czasopisma.pan.pl/dlibra/publication/edition/130799
T2 - Archives of Control Sciences
ER -