Linear time recognition of P4-indifference graphs

Michel Habib (1) , Christophe Paul (2) , Laurent Viennot (3)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 ALGCO - Algorithmes, Graphes et Combinatoire
3 HIPERCOM - High performance communication

A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Web

Michel Habib, Christophe Paul, Laurent Viennot. Linear time recognition of P4-indifference graphs. Discrete Mathematics and Theoretical Computer Science, 2001, Vol. 4 no. 2 (2), pp.173-178. ⟨10.46298/dmtcs.269⟩. ⟨inria-00471619⟩