Some Results on Chromatic Number as a Function of Triangle Count
Some Results on Chromatic Number as a Function of Triangle Count
复制标题
关于色数作为三角形计数函数的一些结果
DOI：
--
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
David G. Harris
中科院分区：
文献类型：
--
作者：
David G. Harris
对于无三角形图的色数，给出了各种强有力的极值结果。三个值得注意的边界是由Poljak & Tuza（1994）和Johansson给出的顶点数、边数和最大度。将这些类型的边界扩展到具有少量三角形的图的工作相对较少。一个值得注意的例外是Alon et. al（1999）对低度数和每个顶点很少三角形的图的色数进行限定的结果；这个边界与无三角形图的边界几乎相同。这种类型的参数化的刚性要小得多，并且已经出现在几十种组合结构中。
A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak & Tuza (1994), and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon et. al (1999) bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid, and has appeared in dozens of combinatorial constructions.
In this paper, we show a similar type of result for $chi(G)$ as a function of the number of vertices $n$, the number of edges $m$, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds.