2015/07/15 by Bornstein, Claudson F., Pinto, Jose W. C., Rautenbach, Dieter +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1507.04258
A graph G has p-intersection number at most d if it is possible to assign to every vertex u of G, a subset S(u) of some ground set U with |U|=d in such a way that distinct vertices u and v of G are adjacent in G if and only if |S(u)∩ S(v)|≥ p. We show that every minimal forbidden induced subgraph for the hereditary class \cal G(d,p) of graphs whose p-intersection number is at most d, has order at most 3⋅ 2d+1+1, and that the exponential dependence on d in this upper bound is necessary. For p∈ \ d-1,d-2\, we provide more explicit results characterizing the graphs in \cal G(d,p) without isolated/universal vertices using forbidden induced subgraphs.