Equitable Colorings Of Corona Multiproducts Of Graphs

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 kn...

Full description

Bibliographic Details
Main Authors:	Furmánczyk Hanna, Kubale Marek, Mkrtchyan Vahan V.
Format:	Article
Language:	English
Published:	Sciendo 2017-11-01
Series:	Discussiones Mathematicae Graph Theory
Subjects:	corona graph equitable chromatic number equitable coloring conjecture equitable graph coloring multiproduct of graphs NP-completeness polynomial algorithm.
Online Access:	http://www.degruyter.com/view/j/dmgt.2017.37.issue-4/dmgt.1992/dmgt.1992.xml?format=INT

id	doaj-art-a6fe15ed05d445bca32d797b8b2b653c
recordtype	oai_dc
spelling	doaj-art-a6fe15ed05d445bca32d797b8b2b653c2018-09-02T19:13:13ZengSciendoDiscussiones Mathematicae Graph Theory2083-58922017-11-013741079109410.7151/dmgt.1992dmgt.1992Equitable Colorings Of Corona Multiproducts Of GraphsFurmánczyk Hanna0Kubale Marek1Mkrtchyan Vahan V.2Institute of Informatics, University of Gdánsk Wita Stwosza 57, 80-952 Gdánsk, PolandDepartment of Algorithms and System Modelling Gdánsk University of Technology Narutowicza 11/12, 80-233 Gdánsk, PolandDepartment of Informatics and Applied Mathematics Yerevan State University, Yerevan, ArmeniaA 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].http://www.degruyter.com/view/j/dmgt.2017.37.issue-4/dmgt.1992/dmgt.1992.xml?format=INTcorona graphequitable chromatic numberequitable coloring conjectureequitable graph coloringmultiproduct of graphsNP-completenesspolynomial algorithm.
institution	Open Data Bank
collection	Open Access Journals
building	Directory of Open Access Journals
language	English
format	Article
author	Furmánczyk Hanna Kubale Marek Mkrtchyan Vahan V.
spellingShingle	Furmánczyk Hanna Kubale Marek Mkrtchyan Vahan V. Equitable Colorings Of Corona Multiproducts Of Graphs Discussiones Mathematicae Graph Theory corona graph equitable chromatic number equitable coloring conjecture equitable graph coloring multiproduct of graphs NP-completeness polynomial algorithm.
author_facet	Furmánczyk Hanna Kubale Marek Mkrtchyan Vahan V.
author_sort	Furmánczyk Hanna
title	Equitable Colorings Of Corona Multiproducts Of Graphs
title_short	Equitable Colorings Of Corona Multiproducts Of Graphs
title_full	Equitable Colorings Of Corona Multiproducts Of Graphs
title_fullStr	Equitable Colorings Of Corona Multiproducts Of Graphs
title_full_unstemmed	Equitable Colorings Of Corona Multiproducts Of Graphs
title_sort	equitable colorings of corona multiproducts of graphs
publisher	Sciendo
series	Discussiones Mathematicae Graph Theory
issn	2083-5892
publishDate	2017-11-01
description	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].
topic	corona graph equitable chromatic number equitable coloring conjecture equitable graph coloring multiproduct of graphs NP-completeness polynomial algorithm.
url	http://www.degruyter.com/view/j/dmgt.2017.37.issue-4/dmgt.1992/dmgt.1992.xml?format=INT
_version_	1612629620399538176

Equitable Colorings Of Corona Multiproducts Of Graphs

Similar Items