Equitable Colorings Of Corona Multiproducts Of Graphs

Hanna Furmánczyk; Marek Kubale; Vahan V. Mkrtchyan

Discussiones Mathematicae Graph Theory (2017)

  • Volume: 37, Issue: 4, page 1079-1094
  • ISSN: 2083-5892

Abstract

top
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].

How to cite

top

Hanna Furmánczyk, Marek Kubale, and Vahan V. Mkrtchyan. "Equitable Colorings Of Corona Multiproducts Of Graphs." Discussiones Mathematicae Graph Theory 37.4 (2017): 1079-1094. <http://eudml.org/doc/288463>.

@article{HannaFurmánczyk2017,
abstract = {A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].},
author = {Hanna Furmánczyk, Marek Kubale, Vahan V. Mkrtchyan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {corona graph; equitable chromatic number; equitable coloring conjecture; equitable graph coloring; multiproduct of graphs; NP-completeness; polynomial algorithm.},
language = {eng},
number = {4},
pages = {1079-1094},
title = {Equitable Colorings Of Corona Multiproducts Of Graphs},
url = {http://eudml.org/doc/288463},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Hanna Furmánczyk
AU - Marek Kubale
AU - Vahan V. Mkrtchyan
TI - Equitable Colorings Of Corona Multiproducts Of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 4
SP - 1079
EP - 1094
AB - A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
LA - eng
KW - corona graph; equitable chromatic number; equitable coloring conjecture; equitable graph coloring; multiproduct of graphs; NP-completeness; polynomial algorithm.
UR - http://eudml.org/doc/288463
ER -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.