Dichotomizing k-vertex-critical H-free graphs for H of order four

Abstract: For

k g e q 3

, we prove (i) there is a finite number of

k

-vertex-critical

(P_{2} + e l l P_{1})

-free graphs and (ii)

k

-vertex-critical

(P_{3} + P_{1})

-free graphs have at most

2 k - 1

vertices. Together with previous research, these results imply the following characterization where

H

is a graph of order four: There is a finite number of

k

-vertex-critical

H

-free graphs for fixed

k g e q 5

if and only if

H

is one of

o v e r l i n e K_{4}, P_{4}, P_{2} + 2 P_{1}

, or

P_{3} + P_{1}

. Our results imply the existence of new polynomial-time certifying algorithms for deciding the

k

-colorability of

(P_{2} + e l l P_{1})

-free graphs for fixed

k

.

This page was built for publication: Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four