Vizing-type bounds for graphs with induced subgraph restrictions

Abstract: For any graphs

G

and

H

, we say that a bound is of Vizing-type if

g a m m a (G s q u a r e H) g e q c g a m m a (G) g a m m a (H)

for some constant

c

. We show several bounds of Vizing-type for graphs

G

with forbidden induced subgraphs. In particular, if

G

is a triangle and

K_{1, r}

-free graph, then for any graph

H

,

g a m m a (G s q u a r e H) g e q f r a c r 2 r - 1 g a m m a (G) g a m m a (H)

. If

G

is a

K_{r}

and

P_{5}

-free graph for some integer

r g e q 2

, then for any graph

H

,

g a m m a (G s q u a r e H) g e q f r a c r - 1 2 r - 3 g a m m a (G) g a m m a (H)

. We do this by bounding the power of

G

,

p i (G)

. We show that if

G

is claw-free and

P_{6}

-free or

K_{4}

and

P_{5}

-free, then for any graph

H

,

g a m m a (G s q u a r e H) g e q g a m m a (G) g a m m a (H)

. Furthermore, we show Vizing-type bounds in terms of the diameter of

G

.

This page was built for publication: Vizing-type bounds for graphs with induced subgraph restrictions