The Feasibility Problem -- the family ${\cal F}$$(G)$ of all induced $G$-free graphs
| Autor: | Caro, Yair, Cassar, Matthew, Lauri, Josef, Zarb, Christina |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | An infinite family of graphs ${\cal F}$ is called feasible if for any pair of integers $(n,m)$, $n \geq 1$, $0 \leq m \leq \binom{n}{2}$, there is a member $G \in {\cal F}$ such that $G$ has $n$ vertices and $m$ edges. We prove that given a graph $G$, the family ${\cal F}$$(G)$ of all induced $G$-free graphs is feasible if and only if $G$ is not $K_k$, $K_k\backslash K_2$, $\overline{K_k}$, $\overline{K_k\backslash K_2}$, for $k \geq 2$. |
| Databáze: | arXiv |
| Externí odkaz: |
|