Can I read Some Results on Chromatic Number as a Function of Triangle Count on EtoBox?

Some Results on Chromatic Number as a Function of Triangle Count by Harris, David G. is a scholarly article available to read on EtoBox.

What is Some Results on Chromatic Number as a Function of Triangle Count about?

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.

Author

Harris, David G.

Published

2016

Language

EN