Circumference, chromatic number and online coloring
Circumference, chromatic number and online coloring
复制标题
DOI：
10.1007/s00493-013-2542-9
复制
发表时间：
2008-09
期刊：
影响因子：
1.1
通讯作者：
A. Diwan;Sreyash Kenkre;S. Vishwanathan
中科院分区：
文献类型：
--
作者：
A. Diwan;Sreyash Kenkre;S. Vishwanathan
Erdinger证明了如果G是一个色数至少k ≥3的无三角形图，则它包含一个长度至少k2 −o（1）的奇圈[13，15]。到目前为止，没有比线性界（[3]，[16]中的问题5.1.55）更好的了。我们证明了G包含一个长度至少为Ω（kloglogk）的奇圈，从而进一步证明了这一猜想.埃尔德什猜想已知对围长至少为5的图成立。证明了如果围长为4的图是C5 free的，则Erdens猜想成立.当顶点数不太大时，我们可以证明χ的更好的界。我们还给出了最多有长度为1modk的圈、最多有长度为2modk的圈或没有长度为3modk的圈的图的色数的界。我们的技术基本上包括使用深度优先搜索树分解成有序的路径，然后馈送到一个在线着色算法的图形。利用这一技巧，我们给出了一些旧结果的简单证明，也得到了一些其他的结果。我们还得到了一个下界的颜色的数量，在线着色算法需要使用的颜色三角形自由图。
Erdős conjectured that ifGis a triangle free graph of chromatic number at leastk≥3, then it contains an odd cycle of length at leastk2−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 thatGcontains an odd cycle of length at leastΩ(klog logk). Erdős’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four isC5free, 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 mostrcycles of length 1 modk, or at mostscycles of length 2 modk, or no cycles of length 3 modk. 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.