Name
Abstract | ||
|---|---|---|
A classical result from graph theory is that every graph with chromatic number chi > t contains a subgraph with all degrees at least t, and therefore contains a copy of every t-edge tree. Bohman, Frieze, and Mubayi recently posed this problem for r-uniform hypergraphs. An r-tree is a connected r-uniform hypergraph with no pair of edges intersecting in more than one vertex, and no sequence of distinct vertices and edges (v(1), e(1), ..., v(k), e(k)) with all e(i) (sic) {v(i), v(i+1)}, where we take v(k+1) to the v(1). Bohman, Frieze, and Mubayi proved that chi > 2rt is sufficient to embed every r-tree with t edges, and asked whether the dependence on r was necessary. In this note, we completely solve their problem, proving the tight result that chi > t is sufficient to embed any r-tree with t edges. |
Year | Venue | Keywords |
|---|---|---|
2009 | ELECTRONIC JOURNAL OF COMBINATORICS | graph theory |
DocType | Volume | Issue |
Journal | 16.0 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 3 | 0.48 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |