Abstract
Erdős conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k 2−o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erdős’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C 5 free, then Erdős’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Introduction To Algorithms — Second Edition, The MIT Press, 2001.
P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp: The number of cycle lengths in graphs of given minimum degree and girth, Discrete Mathematics 200 (1999) 55–60.
A. Gyárfás: Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992) 41–48.
M. Halldórsson, M. Szegedy: Lower Bounds for On-Line Graph Coloring, Symposium on Discrete Algorithms, SODA, 211–216, (1992).
S. Kenkre, S. Vishwanathan: A Bound On The Chromatic Number Using The Longest Odd Cycle Length, Journal of Graph Theory 54(4) (2007), 267–276.
H. Kierstead: Coloring Graphs Online, Online Algorithms, LNCS vol. 1442, Springer Berlin/Heidelberg, 1998.
L. Lovász, M. Saks, W. T. Trotter: An Online Graph Coloring Algorithm With Sublinear Performance Ratio, Discrete Mathematics 75 (1989), 319–325.
Ch. Löwenstein, D. Rautenbach, I. Schiermeyer: Cycle length parities and the chromatic number, Journal of Graph Theory 64(3) (2010), 210–218.
M. Molloy, Bruce Reed: Graph Coloring and the Probabilistic Method, Springer Berlin, 2000.
P. Mihók, I. Schiermeyer: Cycle lengths and chromatic number of graphs, Discrete Mathematics 286 (2004), 147–149.
A. Nilli: Triangle-free graphs with large chromatic numbers, Discrete Mathematics 211 (2000), 261–262.
I. Schiermeyer, B. Randerath: Chromatic Number of Graphs each Path of which is 3-colorable, Result. Math 41 (2002), 150–155.
B. Sudakov, J. Verstraëte: Cycle lengths in sparse graphs, Preprint. To be published in Combinatorica.
Zs. Tuza: Graph coloring in linear time, Journal of Combinatorial Theory (B) 55 (1992), 236–243.
J. Verstraëte: Extremal Problems for Cycles in Graphs, Invited lecture. Oberwolfach Combinatorics Workshop. January 6–12th 2008, http://owpdb.mfo.de/show workshop?id=609.
D. West: Introduction to Graph Theory — second edition, Prentice Hall, 2001.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Diwan, A.A., Kenkre, S. & Vishwanathan, S. Circumference, chromatic number and online coloring. Combinatorica 33, 319–334 (2013). https://doi.org/10.1007/s00493-013-2542-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-013-2542-9