The harmonic sums of odd-cycle lengths diverges for graphs of infinite chromatic number
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A problem on odd cycles (proposed by
Erdös and Hajnal [1])
Let \( G\) be a graph of infinite chromatic number and let
\( n_1
< n_2 < \dots \) be the sequence consisting of lengths
of odd cycles in \( G\). Is it true that
\(\displaystyle \sum \frac 1 {n_i} = \infty?\)
Gyárfás, Komlós and Szemerédi [2] proved that the set of all cycle lengths has positive upper density.
Bibliography | |
---|---|
1 | P. Erdös, Some recent progress on extremal problems in graph theory, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congress. Numer. XIV, 3-14, Utilitas Math., Winnipeg, Man., 1975. |
2 | A. Gyárfás, J. Komlós and A. Szemerédi, On the distribution of cycle lengths in graphs, J. Graph Theory 8 (1984), 441-462. |