List 3-coloring P_t-free graphs with no induced 1-subdivision of K₁ , s

Abstract: Let

s

and

t

be positive integers. We use

P_{t}

to denote the path with

t

vertices and

K_{1, s}

to denote the complete bipartite graph with parts of size

1

and

s

respectively. The one-subdivision of

K_{1, s}

is obtained by replacing every edge

u, v

of

K_{1, s}

by two edges

u, w

and

v, w

with a new vertex

w

. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of

P_{t}

-free graph with no induced 1-subdivision of

K_{1, s}

.

Recommendations

Cites Work

Cited In (9)

This page was built for publication: List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)