Equitable coloring of corona products of cubic graphs is harder than ordinary coloring

DOI10.26493/1855-3974.687.99BzbMATH Open1347.05064arXiv1409.0650OpenAlexW2964017825WikidataQ129367202 ScholiaQ129367202MaRDI QIDQ2827784FDOQ2827784

Authors: Hanna Furmańczyk, Marek Kubale 

Publication date: 21 October 2016

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

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 emph{equitable chromatic number} of $G$ and it is denoted by $ch{i}_{=}(G)$. In this paper the problem of determinig $ch{i}_{=}$ for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses $ch{i}_{=}(G)$ or $ch{i}_{=}(G)+1$ colors. Our algorithm is best possible, unless $P=NP$. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.

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

Recommendations

• Equitable total coloring of corona of cubic graphs
• Equitable coloring of corona products of graphs
• Equitable colorings of corona multiproducts of graphs
• Equitable coloring on corona graph of graphs
• On equitable coloring of extented corona of some graphs
• Equitable colorings of Kronecker products of graphs
• Equitable colorings of a special class of Cartesian products of graphs
• On the equitable total chromatic number of cubic graphs
• Equitable colorings of Cartesian products of graphs
• Equitable coloring of some convex polytope graphs

zbMATH Keywords

cubic graphNP-hardnesspolynomial algorithmequitable chromatic numbercorona graphequitable graph coloring

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cited In (11)

• Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
• Equitable colorings of \(l\)-corona products of cubic graphs
• Energy and basic reproduction number of n-Corona graphs prior to order 1
• Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
• On the \(r\)-dynamic coloring of subdivision-edge coronas of a path
• Equitable total coloring of corona of cubic graphs
• Equitable coloring on corona graph of graphs
• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
• Equitable coloring of corona products of graphs
• Equitable colorings of corona multiproducts of graphs
• Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms

This page was built for publication: Equitable coloring of corona products of cubic graphs is harder than ordinary coloring

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