𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Complexity of Finding Paths in Graphs with Bounded Independence Number

✍ Scribed by Nickelsen, Arfst; Tantau, Till

Book ID
118181299
Publisher
Society for Industrial and Applied Mathematics
Year
2005
Tongue
English
Weight
289 KB
Volume
34
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

An upper bound for the path number of a
An upper bound for the path number of a graph
✍ Alan Donald πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ LovΓ‘sz has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≀ 1/2 __u__ + __g__ ‐ 1 ≀ __n__ ‐ 1, where __n__ is the total numbe