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

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

c h i_{r =}^{*} (G)

, is the minimum

k

such that

G

is

r

-equitably

k^{'}

-colorable for all

k^{'} g e k

. Let

G i m e s H

denote the Kronecker product of graphs

G

and

H

. In this paper, we completely determine the exact value of

c h i_{r =}^{*} (K_{m} i m e s K_{n})

for general

m, n

and

r

. As a consequence, we show that for

r g e 2

, if

n g e f r a c 1 r - 1 (m + r) (m + 2 r - 1)

then

K_{m} i m e s K_{n}

and its spanning supergraph

K_{m (n)}

have the same

r

-equitable colorability, and in particular

c h i_{r =}^{*} (K_{m} i m e s K_{n}) = c h i_{r =}^{*} (K_{m (n)})

, where

K_{m (n)}

is the complete

m

-partite graph with

n

vertices in each part.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: On \(r\)-equitable chromatic threshold of Kronecker products of complete graphs