Grinberg-Introduction-Graph-Theory · Problem 6.1

Colorings

Mathematics — Graph Theory · proper-colorings

Problem

Let

G

be a simple graph with

n

vertices. Let

k

be a positive integer. Prove the following: (a) If

G

has a proper

k

-coloring, then

G

has no subgraph isomorphic to

K_{k+1}

. (b) If

k \geq n - 2

, then the converse to part (a) also holds: If

G

has no subgraph isomorphic to

K_{k+1}

, then

G

has a proper

k

-coloring. (c) Does the converse to part (a) hold for

k < n - 2

as well? Specifically, does it hold for

n = 5

and

k = 2