Name
Abstract | ||
|---|---|---|
While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on
$$P_k$$
-free graphs. They proved that any graph G with a proper vertex coloring and no path of length
$$2k+1$$
with end vertices of different colors has at most 2kn edges. We show that Erdős and Gallai’s original sharp upper bound of kn holds for their problem as well. We also introduce a version of this problem for trees and present a generalization of the Erdős-Sós conjecture. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00373-019-02026-1 | Graphs and Combinatorics |
Keywords | Field | DocType |
Extremal, Paths, Cycles, Trees, Vertex colored | Graph,Combinatorics,Colored,Vertex (geometry),Upper and lower bounds,Constraint graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 3 | 0911-0119 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nika Salia | 1 | 0 | 0.68 |
| Casey Tompkins | 2 | 4 | 2.48 |
| Oscar Zamora | 3 | 1 | 1.07 |