pith. sign in

arxiv: 1310.2188 · v1 · pith:AYHYQQNDnew · submitted 2013-10-08 · 🧮 math.CO · cs.DM

On r-equitable chromatic threshold of Kronecker products of complete graphs

classification 🧮 math.CO cs.DM
keywords timesgraphchromaticcolorablecompleteequitableequitablygraphs
0
0 comments X
read the original abstract

A graph $G$ is $r$-equitably $k$-colorable if its vertex set can be partitioned into $k$ independent sets, any two of which differ in size by at most $r$. The $r$-equitable chromatic threshold of a graph $G$, denoted by $\chi_{r=}^*(G)$, is the minimum $k$ such that $G$ is $r$-equitably $k'$-colorable for all $k'\ge k$. Let $G\times H$ denote the Kronecker product of graphs $G$ and $H$. In this paper, we completely determine the exact value of $\chi_{r=}^*(K_m\times K_n)$ for general $m,n$ and $r$. As a consequence, we show that for $r\ge 2$, if $n\ge \frac{1}{r-1}(m+r)(m+2r-1)$ then $K_m\times K_n$ and its spanning supergraph $K_{m(n)}$ have the same $r$-equitable colorability, and in particular $\chi_{r=}^*(K_m\times K_n)=\chi_{r=}^*(K_{m(n)})$, where $K_{m(n)}$ is the complete $m$-partite graph with $n$ vertices in each part.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.