On r-equitable coloring of complete multipartite graphs

DOI10.11650/TJM.17.2013.2666zbMATH Open1280.05048arXiv1211.4340OpenAlexW2091660961MaRDI QIDQ390073FDOQ390073

Authors: Chih-Hung Yen 

Publication date: 22 January 2014

Published in: Taiwanese Journal of Mathematics (Search for Journal in Brave)

Abstract: Let $rgeqslant0$ and $kgeqslant1$ be integers. We say that a graph $G$ has an $r$-equitable $k$-coloring if there exists a proper $k$-coloring of $G$ such that the sizes of any two color classes differ by at most $r$. The least $k$ such that a graph $G$ has an $r$-equitable $k$-coloring is denoted by $ch{i}_{r=}(G)$, and the least $n$ such that a graph $G$ has an $r$-equitable $k$-coloring for all $kgeqslantn$ is denoted by $ch{i}_{r=}^{\ast }(G)$. In this paper, we propose a necessary and sufficient condition for a complete multipartite graph $G$ to have an $r$-equitable $k$-coloring, and also give exact values of $ch{i}_{r=}(G)$ and $ch{i}_{r=}^{\ast }(G)$.

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

Recommendations

• On equitable coloring of complete \(r\)-partite graphs
• Equitable chromatic number of complete multipartite graphs
• Equitable colorings of line graphs and complete \(r\)-partite graphs
• On \(r\)-equitable colorings of bipartite graphs
• Proofs for some known results of equitable coloring

zbMATH Keywords

equitable coloringcomplete multipartite graph\(r\)-equitable chromatic number\(r\)-equitable chromatic threshold\(r\)-equitable coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (12)

• On \(r\)-equitable chromatic threshold of Kronecker products of complete graphs
• A note on \(r\)-equitable \(k\)-colorings of trees
• Equitable total coloring of complete $r$-partite $p$-balanced graphs
• Determining equitable total chromatic number for infinite classes of complete \(r\)-partite graphs
• On \(r\)-equitable colorings of bipartite graphs
• On equitable coloring of complete \(r\)-partite graphs
• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs
• On the equitable chromatic number of complete \(n\)-partite graphs
• \((N, p)\)-equitable \(b\)-coloring of graphs
• Equitable defective colorings of complete bipartite graphs
• Equitable chromatic number of complete multipartite graphs
• Proofs for some known results of equitable coloring

This page was built for publication: On \(r\)-equitable coloring of complete multipartite graphs

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