Record Details

Circumference, chromatic number and online coloring

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Circumference, chromatic number and online coloring
 
Creator DIWAN, AA
KENKRE, S
VISHWANATHAN, S
 
Subject CYCLE LENGTHS
GRAPHS
 
Description ErdAs conjectured that if G is a triangle free graph of chromatic number at least ka parts per thousand yen3, 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 Omega(k log logk). ErdAs' 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 ErdAs' conjecture holds. When the number of vertices is not too large we can prove better bounds on chi. 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.
 
Publisher SPRINGER
 
Date 2014-10-16T14:23:03Z
2014-10-16T14:23:03Z
2013
 
Type Article
 
Identifier COMBINATORICA, 33(3)319-334
0209-9683
1439-6912
http://dx.doi.org/10.1007/s00493-013-2542-9
http://dspace.library.iitb.ac.in/jspui/handle/100/15774
 
Language en