𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Counting H-free graphs

✍ Scribed by Hans Jürgen Prömel; Angelika Steger

Book ID
103060896
Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
269 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let Forb",, (H) denote the class of all H-free graphs on n (labelled) vertices with m edges. In this note we estimate the cardinality of IForb,, by establishing good bounds for the probability that a random graph in the G(n,m)-model does not contain a given subgraph.

📜 SIMILAR VOLUMES

Counting Claw-Free Cubic Graphs
Counting Claw-Free Cubic Graphs
✍ Palmer, Edgar M.; Read, Ronald C.; Robinson, Robert W. 📂 Article 📅 2002 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 121 KB
Random maximal H-free graphs
Random maximal H-free graphs
✍ Deryk Osthus; Anusch Taraz 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB 👁 2 views

Given a graph H, a random maximal H-free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p = 0 start with the empty graph and increase p gradually. Each time a new

Choosability on H-free graphs
Choosability on H-free graphs
✍ Golovach, Petr A.; Heggernes, Pinar; van ʼt Hof, Pim; Paulusma, Daniël 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 156 KB
Counting cubic graphs
Counting cubic graphs
✍ Robert W. Robinson 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB
Counting disk graphs
Counting disk graphs
✍ Colin McDiarmid; Tobias Müller 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 181 KB