✦ LIBER ✦

A note on perfect orders

✍ Scribed by C.T. Hoáng; N.V.R. Mahadev

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 852 KB
Volume: 74
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90200-8

No coin nor oath required. For personal study only.

✦ Synopsis

Perfectly orderable graphs were introduced by Chvfital in 1984. Since then, several classes of perfectly orderable graphs have been identified. In this paper, we establish three new results on perfectly orderable graphs. First, we prove that every graph with Dilworth number at most three has a simplicial vertex, in the graph or in its complement. Second, we provide a characterization of graphs G with this property: each maximal vertex of G is simplicial in the complement of G. Finally, we introduce the notion of a locally perfect order and show that every arborescence-comparability graph admits a locally perfect order.

📜 SIMILAR VOLUMES

A Note on Perfect Isometries

✍ Geoffrey R. Robinson 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 94 KB

## Ž . B which take constant non-zero ¨alues on p-singular elements. 1 Furthermore, it is always possible to modify the perfect isometry so that it sends the trivial character of H to the trivial character of G.

A note on graphs and sphere orders

✍ Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract A partially ordered set __P__ is called a __k‐sphere order__ if one can assign to each element a ∈ __P__ a ball __B__~__a__~ in __R^k^__ so that __a__ < __b__ iff __B__~__a__~ ⊂ __B__~__b__~. To a graph __G__ = (__V,E__) associate a poset __P__(__G__) whose elements are the vertices and

A note on Ki-perfect graphs

✍ Jason I. Brown; Derek G. Corneil; A. Ridha Mahjoub 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract __Ki__‐perfect graphs are a special instance of __F ‐ G__ perfect graphs, where __F__ and __G__ are fixed graphs with __F__ a partial subgraph of __G.__ Given __S__, a collection of __G__‐subgraphs of graph __K__, an __F ‐ G__ cover of __S__ is a set of __T__ of __F__‐subgraphs of __K__

A note on path-perfect graphs

✍ John Frederick Fink; H.Joseph Straight 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 498 KB

In this paper we explore the c:oncept of factoring a graph into non-isomorphic paths. Lel Pi denote the path of length i. We SAY that a graph G having $n(n + 1) edges is path-perfect if E( G) can be partitioned as E, UE, !J l \* l U & such that the subgraph of G induced by 32i is isomorphic to Pr, f

A note on perfect Gaussian elimination

✍ Martin Charles Golumbic 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 133 KB

A note on vertex orders for stability nu

A note on vertex orders for stability number

✍ Mahadev, N. V. R.; Reed, B. A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

We investigate vertex orders that can be used to obtain maximum stable sets by a simple greedy algorithm in polynomial time in some classes of graphs. We characterize a class of graphs for which the stability number can be obtained by a simple greedy algorithm. This class properly contains previousl