|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On r-equitable chromatic threshold of Kronecker products of complete graphs | | Wei Wang
; Zhidan Yan
; Xin Zhang
; | | Date: |
8 Oct 2013 | | 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 imes H$ denote the Kronecker product
of graphs $G$ and $H$. In this paper, we completely determine the exact value
of $chi_{r=}^*(K_m imes K_n)$ for general $m,n$ and $r$. As a consequence, we
show that for $rge 2$, if $nge frac{1}{r-1}(m+r)(m+2r-1)$ then $K_m imes
K_n$ and its spanning supergraph $K_{m(n)}$ have the same $r$-equitable
colorability, and in particular $chi_{r=}^*(K_m imes
K_n)=chi_{r=}^*(K_{m(n)})$, where $K_{m(n)}$ is the complete $m$-partite graph
with $n$ vertices in each part. | | Source: | arXiv, 1310.2188 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER