P 4-Colorings and P 4-Bipartite Graphs

Abstract

A vertex partition of a graph into disjoint subsets V i s is said to be a P 4-free coloring if each color class V i induces a subgraph without chordless path on four vertices (denoted by P 4). Examples of P 4-free 2-colorable graphs (also called P 4-bipartite graphs) include parity graphs and graphs with ``few'' P 4 s like P 4-reducible and P 4-sparse graphs. We prove that, given k≥2, P 4-Free k-Colorability is NP-complete even for comparability graphs, and for P 5-free graphs. We then discuss the recognition, perfection and the Strong Perfect Graph Conjecture (SPGC) for P 4-bipartite graphs with special P 4-structure. In particular, we show that the SPGC is true for P 4-bipartite graphs with one P 3-free color class meeting every P 4 at a midpoint.