Equitable chromatic number of complete multipartite graphs
type: Item
instance of: scholarly article
title: Equitable chromatic number of complete multipartite graphs
zbMATH Open document ID: 1027.05038
author: Dorothee Blum
author: Denise Torrey
author: Richard H. Hammack
published in: Missouri Journal of Mathematical Sciences
publication date: 2004-01-07T00:00:00Z
review text: An equitable \(n\)-coloring of a graph \(G\) is a proper \(n\)-coloring of \(G\) such that the color classes \(V_i\) satisfy the condition \(||V_i|-|V_j||\leq 1\) for all \(i,j\) with \(1 \leq i\), \(j \leq n\). The equitable chromatic number \(\chi_e(G)\) is the smallest integer \(n\) such that \(G\) can be equitably colored with \(n\) colors. Given positive integers \(p_1, p_2, \dots , p_k\), the complete \(k\)-partite graph \(K(p_1, p_2, \dots , p_k)\) is the graph whose vertex set is the union \(P_1 \cup P_2 \cup \cdots \cup P_k\) of \(k\) partite sets, each \(P_i\) consists of \(p_i\) vertices, and two vertices are adjacent if and only if they belong to different partite sets. The main theorem of this paper says that \(\chi_e(K(p_1, p_2, \dots , p_k))=\sum_{i=1}^k(\lfloor p_i/x \rfloor - \lfloor \lfloor p_i/x \rfloor - p_i/(x+1) \rfloor)\), where \(x\) is the largest integer satisfying \(p_i/(x+1) \leq \lfloor p_i/x \rfloor\) for each \(i\) with \(1 \leq i \leq k\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1982156
zbMATH Keywords: equitable coloring
zbMATH Keywords: multipartite graph
MaRDI profile type: Publication
Recommended article: On the equitable chromatic number of complete \(n\)-partite graphs
Recommended article: Q4604345
Recommended article: Equitable total chromatic number of splitting graph
Recommended article: Equitable total chromatic numbers of the square graphs of some graphs
Recommended article: Determining equitable total chromatic number for infinite classes of complete \(r\)-partite graphs
Recommended article: A study of the total chromatic number of equibipartite graphs
Recommended article: Total colorings of equibipartite graphs
Recommended article: On equitable coloring of complete \(r\)-partite graphs
Recommended article: On \(r\)-equitable coloring of complete multipartite graphs
Recommended article: Equipartite edge colouring of multigraphs
description: scientific article; zbMATH DE number 1982156