P_4-Colorings and P_4-Bipartite Graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.109-122
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958951
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:51:53
Dernière modification le : vendredi 23 novembre 2018 - 15:38:02
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:03:47

Fichier

dm040204.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958951, version 1

Collections

Citation

Chinh T. Hoàng, Van Bang Le. P_4-Colorings and P_4-Bipartite Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.109-122. 〈hal-00958951〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

419