Premium
A characterization of P 4 ‐indifference graphs
Author(s) -
Hoàng Chính T.,
Maffray Frédéric,
Noy Marc
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199907)31:3<155::aid-jgt1>3.0.co;2-r
Subject(s) - combinatorics , mathematics , cograph , graph , characterization (materials science) , chordal graph , split graph , discrete mathematics , induced path , 1 planar graph , longest path problem , physics , optics
A graph is a P 4 ‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a . P 4 ‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P 4 ‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999