Chinh T. Hoàng ; Van Bang Le - P_4-Colorings and P_4-Bipartite Graphs

dmtcs:272 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2 -
P_4-Colorings and P_4-Bipartite GraphsArticle

Authors: Chinh T. Hoàng 1; Van Bang Le

  • 1 Department of Physics and Computer Science [Waterloo]

A vertex partition of a graph into disjoint subsets V_is 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_4s like P_4-reducible and P_4-sparse graphs. We prove that, given k≥ 2, \emphP_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.

Volume: Vol. 4 no. 2
Published on: January 1, 2001
Imported on: March 26, 2015
Keywords: Perfect graph,the Strong Perfect Graph Conjectrue,graph partition,cograph,NP-completeness,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada


Consultation statistics

This page has been seen 249 times.
This article's PDF has been downloaded 435 times.