✦ LIBER ✦

A characterization ofP4-indifference graphs

✍ Scribed by Ho�ng, Ch�nh T.; Maffray, Fr�d�ric; Noy, Marc

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 237 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199907)31:3<155::aid-jgt1>3.0.co;2-r

No coin nor oath required. For personal study only.

✦ Synopsis

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 4indifference graphs by forbidden induced subgraphs.

📜 SIMILAR VOLUMES

A Characterization ofp-Radical Groups

✍ A. Laradji 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 100 KB

A characterization of Seymour graphs

✍ Ageev, A. A.; Kostochka, A. V.; Szigeti, Z. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T -cuts is equal to the cardinality of a minimum T -join for every even subset T of V (G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour

A characterization of ptolemaic graphs

✍ Edward Howorka 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 466 KB

A connected graph G is ptolernaic provided that for each four vertices u,, 1 5 i 5 4, of G, the six distances d, =dG (u,ui), i f j satisfy the inequality d,2d34 5 d,3d24 + d,4d23 (shown by Ptolemy t o hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showe

A characterization of ?-outerplanar grap

A characterization of ?-outerplanar graphs

✍ Wargo, Lawrence 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 528 KB

Chartrand and Harary have shown that if G is a non-outerplanar graph such that, for every edge e, both the deletion G \ e and the contraction G/e of e from G are outerplanar, then G is isomorphic to K4 or K2,3. An a-outerplanar graph is a graph which is not outerplanar such that, for some edge a , b

A characterization of radius-critical gr

A characterization of radius-critical graphs

✍ Siemion Fajtlowicz 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs. 1. By a graph we shall mean here a finite, simple, undirected graph. For a connected graph the distance between two

A characterization of partially dual gra

A characterization of partially dual graphs

✍ Iain Moffatt 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 332 KB

In this article, we extend the recently introduced concept of partially dual ribbon graphs to graphs. We then go on to characterize partial duality of graphs in terms of bijections between edge sets of corresponding graphs. This result generalizes a well-known result of J. Edmonds in which natural d