𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Almost all comparability graphs are UPO

✍ Scribed by Rolf H. Möhring

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
430 KB
Volume
50
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

An undirected graph G is called a comparability graph if there exists an orientation of its edges such that the resulting relation on its vertex set is a partial order P. A comparability graph is UPO (i.e. uniquely partially orderable) if, except for its dual p-x, there is only one such partial order P. In this paper we show that lira,__*** G(rg UPO)IG(n) = 1, where G(n) and G(n, UPO) denote, respectively, the number of comparability graphs and UPO-comparability graphs on n vertices. As a consequence, G(n) is asymptotically equal to half the number of partial orders on n elements.

📜 SIMILAR VOLUMES

Almost all Cayley graphs are hamiltonian
Almost all Cayley graphs are hamiltonian
✍ Meng Jixiang; Huang Qiongxiang 📂 Article 📅 1996 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 278 KB
Almost all graphs with average degree 4
Almost all graphs with average degree 4 are 3-colorable
✍ Dimitris Achlioptas; Cristopher Moore 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree dp4:03; i.e., Gðn; p ¼ d=nÞ; are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.

Almost All Maps Are Asymmetric
Almost All Maps Are Asymmetric
✍ L.B. Richmond; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 291 KB

We give a simple proof of the fact that for a wide variety of classes of maps on surfaces, almost all maps in the class are asymmetric. Our method is based on recent results on the appearance of submaps in the classes. 'c. 1995 Academic Press, Inc.