Name
Abstract | ||
|---|---|---|
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 G(d,p) of graphs whose p-intersection number is at most d, has order at most (2d+1)2, 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 G(d,p) without isolated/universal vertices using forbidden induced subgraphs. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2015.09.022 | Discrete Mathematics |
Keywords | Field | DocType |
Intersection graph,Intersection number,p-intersection number,Forbidden induced subgraph | Discrete mathematics,Combinatorics,Exponential function,Bound graph,Vertex (geometry),Intersection number,Upper and lower bounds,Induced subgraph,Intersection graph,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
339 | 2 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claudson F. Bornstein | 1 | 110 | 10.93 |
| José W. C. Pinto | 2 | 0 | 0.34 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |