Premium
Random maximal H ‐free graphs *
Author(s) -
Osthus Deryk,
Taraz Anusch
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200101)18:1<61::aid-rsa5>3.0.co;2-t
Subject(s) - combinatorics , random graph , mathematics , complement graph , random regular graph , line graph , null graph , discrete mathematics , graph , voltage graph , regular graph , pathwidth
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 edge is born, it is included in the graph if this does not create a copy of H . The question is then how many edges such a graph will have when p =1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2‐balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than and chromatic number n * y 1/(‐1)+ o (1), which improves on previous bounds for >3. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 61–82, 2001