Path-Bicolorable Graphs

In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For

k

 ≥ 2, a graph

G

 = (

V

,

E

) is

P

k

-bicolorable

if its vertex set

V

can be partitioned into two subsets (i.e., colors)

V

1

and

V

2

such that for every induced

P

k

(i.e., path with exactly

k

 − 1 edges and

k

vertices) in

G

, the two colors alternate along the

P

k

, i.e., no two consecutive vertices of the

P

k

belong to the same color

V

i

,

i

 = 1,2. Obviously, a graph is bipartite if and only if is

P

2

-bicolorable, every graph is

P

k

-bicolorable for some

k

and if

G

is

P

k

-bicolorable then it is

P

k

 + 1

-bicolorable. The notion of

P

k

-bicolorable graphs is motivated by a similar notion of cycle-bicolorable graphs introduced in connection with chordal probe graphs. Moreover,

P

3

- and

P

4

-bicolorable graphs are closely related to various other concepts such as 2-subcolorable graphs,

P

4

-bipartite graphs and alternately orientable graphs.

We give a structural characterization of

P

3

-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of

P

4

-bicolorable graphs in terms of forbidden subgraphs.