Equitable chromatic threshold of direct products of complete graphs.

MaRDI QIDQ4982928zbMATH OpenFDO

Authors Zhidan Yan, Wei Wang

Publication date 13 April 2015

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

zbMATH Keywords

complete graphdirect productequitable chromatic thresholdequitable coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. The equitable chromatic threshold of a graph $G$, denoted by $ch{i}_{=}^{\ast }(G)$, is the minimum $k$ such that $G$ is equitably $k^{p}rime$-colorable for all $k^{p}rimegek$. Let $GimesH$ denote the direct product of graphs $G$ and $H$. For $ngemge2$ we prove that $ch{i}_{=}^{\ast }(K_{m}imes{K}_n)$ equals $lceilfracmnm+1ceil$ if $nequiv2,\mathrm{...},m(extupmodm+1)$, and equals $mlceilfracn{s}^{s}tarceil$ if $nequiv0,1(extupmodm+1)$, where $s^{s}tar$ is the minimum positive integer such that $s^{s}tarmidn$ and $s^{s}targem+2.$

Recommendations

• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs
• Equitable coloring of Cartesian product of some graphs.
• Equitable colorings of Kronecker products of graphs
• Equitable colorings of Cartesian products with balanced complete multipartite graphs
• Equitable colorings of Cartesian products of graphs

Cited in

(2)

• Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs
• On r-equitable chromatic threshold of Kronecker products of complete graphs

This page was built for publication: Equitable chromatic threshold of direct products of complete graphs.

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