کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421152 | 684147 | 2014 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On rr-equitable chromatic threshold of Kronecker products of complete graphs On rr-equitable chromatic threshold of Kronecker products of complete graphs](/preview/png/421152.png)
Let rr and kk be positive integers. A graph GG is rr-equitably kk-colorable if its vertex set can be partitioned into kk independent sets, any two of which differ in size by at most rr. The rr-equitable chromatic threshold of a graph GG, denoted by χr=∗(G), is the minimum kk such that GG is rr-equitably k′k′-colorable for all k′≥kk′≥k. Let G×HG×H denote the Kronecker product of graphs GG and HH. In this paper, we completely determine the exact value of χr=∗(Km×Kn) for general m,nm,n and rr. As a consequence, we show that for r≥2r≥2, if n≥1r−1(m+r)(m+2r−1) then Km×KnKm×Kn and its spanning supergraph Km(n)Km(n) have the same rr-equitable colorability, and in particular χr=∗(Km×Kn)=χr=∗(Km(n)), where Km(n)Km(n) is the complete mm-partite graph with nn vertices in each part.
Journal: Discrete Applied Mathematics - Volume 175, 1 October 2014, Pages 129–134