Discrete Mathematics & Theoretical Computer Science, Vol 4, No 2 (2001)

Font Size:  Small  Medium  Large

P4-Colorings and P4-Bipartite Graphs

Chính T. Hoàng, Van Bang Le


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

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page