Equitable colorings of corona multiproducts of graphs

Hanna Furmańczyk , Marek Kubale , Vahan V. Mkrtchyan

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 Furmańczyk (FMPI/II)
Hanna Furmańczyk,,
- Institute of Informatics
, Marek Kubale
Marek Kubale,,
-
, Vahan V. Mkrtchyan
Vahan V. Mkrtchyan,,
-
Journal seriesDiscussiones Mathematicae Graph Theory, ISSN 1234-3099, (A 15 pkt)
Issue year2017
Vol37
No4
Pages1079-1094
Publication size in sheets0.75
Keywords in EnglishCorona graph, equitable chromatic number, equitable coloring conjecture, equitable graph coloring, multiproduct of graphs, NP-completeness, polynomial algorithm
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
DOIDOI:10.7151/dmgt.1992
URL https://www.degruyter.com/downloadpdf/j/dmgt.2017.37.issue-4/dmgt.1992/dmgt.1992.pdf
Languageen angielski
LicenseJournal (articles only); published final; Uznanie Autorstwa - Użycie Niekomercyjne - Bez utworów zależnych (CC-BY-NC-ND); with publication
Score (nominal)15
Score sourcejournalList
ScoreMinisterial score = 15.0, 26-02-2020, ArticleFromJournal
Publication indicators WoS Citations = 1.000; Scopus SNIP (Source Normalised Impact per Paper): 2017 = 1.098; WoS Impact Factor: 2017 = 0.601 (2) - 2017=0.535 (5)
Citation count*
Cite
busy
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?