
arXiv: 1210.6568
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 $χ_{=}(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 $G \circ ^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}.
14 pages, 1 figure
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), polynomial algorithm., Graph operations (line graphs, products, etc.), Corona graph, equitable chromatic number, polynomial algorithm, NP-completeness, np-completeness, equitable graph coloring, Coloring of graphs and hypergraphs, equitable coloring conjecture, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, corona graph, Combinatorics (math.CO), multiproduct of graphs, Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), polynomial algorithm., Graph operations (line graphs, products, etc.), Corona graph, equitable chromatic number, polynomial algorithm, NP-completeness, np-completeness, equitable graph coloring, Coloring of graphs and hypergraphs, equitable coloring conjecture, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, corona graph, Combinatorics (math.CO), multiproduct of graphs, Mathematics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
