Equitable colorings of corona multiproducts of graphs

DOI10.7151/DMGT.1992MaRDI QIDQ2409797zbMATH OpenOpenAlexFDO

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

Publication date 13 October 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1210.6568

zbMATH Keywords

corona graphequitable chromatic numberequitable coloring conjectureequitable graph coloringmultiproduct of graphsNP-completenesspolynomial algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A graph 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 $k$ for which such a coloring exists is known as the equitable chromatic number of $G$ and denoted $ch{i}_{=}(G)$. It is known that this problem is NP-hard in general case and remains so for corona graphs. In "Equitable colorings of Cartesian products of graphs" (2012) Lin and Chang studied equitable coloring of Cartesian products of graphs. In this paper we consider the same model of coloring in the case of corona products of graphs. In particular, we obtain some results regarding the equitable chromatic number for $l$-corona product $Gcir{c}^{l}H$, where $G$ is an equitably 3- or 4-colorable graph and $H$ is an $r$-partite graph, a path, a cycle or a complete graph. Our proofs are 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 Equitable Coloring Conjecture for corona products of such graphs. This paper extends our results from cite{hf}.

Recommendations

• Equitable coloring of corona products of graphs
• Equitable coloring on corona graph of graphs
• On equitable coloring of extented corona of some graphs
• Equitable total coloring of corona of cubic graphs
• Equitable colorings of Kronecker products of graphs
• Equitable colorings of Cartesian products of graphs
• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs
• Equitable colorings of a special class of Cartesian products of graphs
• Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
• Equitable coloring of graph product

Cites work

• A fast algorithm for equitable coloring
• Equitable Coloring
• Equitable coloring and the maximum degree
• Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
• Equitable coloring of corona products of graphs
• Equitable coloring of graph product
• Equitable colorings of bounded treewidth graphs
• Equitable colorings of Cartesian products of graphs
• Equitable colorings of line graphs and complete \(r\)-partite graphs
• Equitable colorings of planar graphs with maximum degree at least nine
• scientific article; zbMATH DE number 1308943 (Why is no real title available?)
• scientific article; zbMATH DE number 1046311 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On equitable and equitable list colorings of series-parallel graphs
• On equitable coloring of bipartite graphs
• On the corona of two graphs
• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

Cited in

(11)

• Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
• Equitable coloring of corona products of graphs
• Equitable coloring on corona graph of graphs
• scientific article; zbMATH DE number 6813611 (Why is no real title available?)
• On equitable coloring of corona of wheels
• Equitable chromatic number of weak modular product of some graphs
• On equitable coloring of extented corona of some graphs
• Energy and basic reproduction number of n-Corona graphs prior to order 1
• Equitable colorings of \(l\)-corona products of cubic graphs
• An improved bound on the chromatic number of the pancake graphs
• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs

This page was built for publication: Equitable colorings of corona multiproducts of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409797)