Sparse vertex cutsets and the maximum degree

Abstract: We show that every graph

G

of maximum degree

D e l t a

and sufficiently large order has a vertex cutset

S

of order at most

D e l t a

that induces a subgraph

G [S]

of maximum degree at most

D e l t a - 3

. For

D e l t a i n 4, 5

, we refine this result by considering also the average degree of

G [S]

. If

G

has no

K_{r, r}

subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most

l e f t (1 - f r a c 1 r c h o o s e 2 i g h t) D e l t a + O (1)

.

This page was built for publication: Sparse vertex cutsets and the maximum degree