A Caro-Wei bound for induced linear forests in graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911096705646592 |
|---|---|
| author | Joret, Gwenaël Petit, Robin |
| author_facet | Joret, Gwenaël Petit, Robin |
| contents | A well-known result due to Caro (1979) and Wei (1981) states that every graph $G$ has an independent set of size at least $\sum_{v\in V(G)} \frac{1}{d(v) + 1}$, where $d(v)$ denotes the degree of vertex $v$. Alon, Kahn, and Seymour (1987) showed the following generalization: For every $k\geq 0$, every graph $G$ has a $k$-degenerate induced subgraph with at least $\sum_{v \in V(G)}\min\{1, \frac {k+1}{d(v)+1}\}$ vertices. In particular, for $k=1$, every graph $G$ with no isolated vertices has an induced forest with at least $\sum_{v\in V(G)} \frac{2}{d(v) + 1}$ vertices. Akbari, Amanihamedani, Mousavi, Nikpey, and Sheybani (2019) conjectured that, if $G$ has minimum degree at least $2$, then one can even find an induced linear forest of that order in $G$, that is, a forest where each component is a path.
In this paper, we prove this conjecture and show a number of related results. In particular, if there is no restriction on the minimum degree of $G$, we show that there are infinitely many ``best possible'' functions $f$ such that $\sum_{v\in V(G)} f(d(v))$ is a lower bound on the maximum order of a linear forest in $G$, and we give a full characterization of all such functions $f$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17568 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Caro-Wei bound for induced linear forests in graphs Joret, Gwenaël Petit, Robin Combinatorics Discrete Mathematics A well-known result due to Caro (1979) and Wei (1981) states that every graph $G$ has an independent set of size at least $\sum_{v\in V(G)} \frac{1}{d(v) + 1}$, where $d(v)$ denotes the degree of vertex $v$. Alon, Kahn, and Seymour (1987) showed the following generalization: For every $k\geq 0$, every graph $G$ has a $k$-degenerate induced subgraph with at least $\sum_{v \in V(G)}\min\{1, \frac {k+1}{d(v)+1}\}$ vertices. In particular, for $k=1$, every graph $G$ with no isolated vertices has an induced forest with at least $\sum_{v\in V(G)} \frac{2}{d(v) + 1}$ vertices. Akbari, Amanihamedani, Mousavi, Nikpey, and Sheybani (2019) conjectured that, if $G$ has minimum degree at least $2$, then one can even find an induced linear forest of that order in $G$, that is, a forest where each component is a path. In this paper, we prove this conjecture and show a number of related results. In particular, if there is no restriction on the minimum degree of $G$, we show that there are infinitely many ``best possible'' functions $f$ such that $\sum_{v\in V(G)} f(d(v))$ is a lower bound on the maximum order of a linear forest in $G$, and we give a full characterization of all such functions $f$. |
| title | A Caro-Wei bound for induced linear forests in graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2403.17568 |