Forbidden induced subgraphs for bounded -intersection number

详细信息    查看全文

• 作者：Claudson F. Bornstein^a ; ^{cbornstein@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; José ; W.C. Pinto^a ; ^{jwcoura@cos.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^b ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; Jayme L. Szwarcfiter^a ; ^{jayme@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Intersection graph ; Intersection number ; pp-intersection number ; Forbidden induced subgraph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：533-538
• 全文大小：420 K

文摘

A graph G$G$ has p$p$-intersection number at most d$d$ if it is possible to assign to every vertex u$u$ of G$G$, a subset S(u)$S\left(u\right)$ of some ground set U$U$ with |U|=d$\left|U\right|=d$ in such a way that distinct vertices u$u$ and v$v$ of G$G$ are adjacent in G$G$ if and only if |S(u)∩S(v)|≥p$|S\left(u\right)\cap S\left(v\right)|\ge p$. We show that every minimal forbidden induced subgraph for the hereditary class G(d,p)$\mathcal{G}(d,p)$ of graphs whose p$p$-intersection number is at most d$d$, has order at most (2^d+1)²${(2^d+1)}^2$, and that the exponential dependence on d$d$ in this upper bound is necessary. For p∈{d−1,d−2}$p\in \{d-1,d-2\}$, we provide more explicit results characterizing the graphs in G(d,p)$\mathcal{G}(d,p)$ without isolated/universal vertices using forbidden induced subgraphs.