×

Some results on chromatic number as a function of triangle count. (English) Zbl 1407.05093

Summary: 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 S. Poljak and Z. Tuza [SIAM J. Discrete Math. 7, No. 2, 307–313 (1994; Zbl 0806.68086)] 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 N. Alon et al. [J. Comb. Theory, Ser. B 77, No. 1, 73–82 (1999; Zbl 1026.05043)] 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.

MSC:

05C15 Coloring of graphs and hypergraphs

References:

[1] M. Ajtai, J. Komlós, and E. Szemerédi, {\it A note on Ramsey numbers}, J. Combin. Theory Ser. A, 29 (1980), pp. 354-360. · Zbl 0455.05045
[2] N. Alon, M. Krivelevich, and B. Sudakov, {\it Coloring graphs with sparse neighborhoods}, J. Combin. Theory Ser. B, 77 (1999), pp. 73-82. · Zbl 1026.05043
[3] A. Blumenthal, B. Lidicky, R. Martin, S. Norin, F. Pfender, and J. Volec, {\it Counterexamples to a Conjecture of Harris on Hall Ratio}, preprint, , 2018. · Zbl 1493.05095
[4] T. Bohman and D. Mubayi, {\it Independence Number of Graphs with a Prescribed Number of Cliques}, preprint, , 2018. · Zbl 1412.05107
[5] Z. Dvor̆ák, P. Ossona de Mendez, and H. Wu, {\it 1-Subdivisions, Fractional Chromatic Number and Hall Ratio}, preprint, , 2018. · Zbl 1474.05334
[6] L. Esperet, R. Kang, and S. Thomassé, {\it Separation Choosability and Dense Bipartite Induced Subgraphs}, preprint, , 2018. · Zbl 1436.05036
[7] J. Gimbel and C. Thomassen, {\it Coloring triangle-free graphs with fixed size}, Discrete Math., 219 (2000), pp. 275-277. · Zbl 0948.05027
[8] M. Kwan, S. Letzter, B. Sudakov, and T. Tran, {\it Dense Induced Bipartite Subgraphs in Triangle-Free Graphs}, preprint, , 2018. · Zbl 1463.05313
[9] J. H. Kim, {\it The Ramsey number \(R(3,t)\) has order of magnitude \(t^2/\log t\)}, Random Structures Algorithms, 7 (1995), pp. 173-207. · Zbl 0832.05084
[10] M. Molloy and B. Reed, {\it Graph Colouring and the Probabilistic Method}, Algorithms Combin., 23, Springer, Heidelberg, 2001. · Zbl 0987.05002
[11] M. Molloy, {\it The list chromatic number of graphs with small clique number}, J. Combin. Theory Ser. B, 134 (2019), pp. 264-284. · Zbl 1402.05076
[12] A. Nilli, {\it Triangle-free graphs with large chromatic number}, Discrete Math., 211 (2000), pp. 261-262. · Zbl 0944.05032
[13] S. Pettie and H. Su, {\it Distributed coloring algorithms for triangle-free graphs}, Inform. and Comput., 243 (2015), pp 263-280. · Zbl 1327.68330
[14] S. Poljak and Z. Tusa, {\it Bipartite subgraphs of triangle-free graphs}, SIAM J. Discrete Math., 7 (1994), pp. 307-313. · Zbl 0806.68086
[15] V. Vu, {\it A general upper bound on the list chromatic number of locally sparse graphs}, Combin. Probab. Comput., 11 (2002), pp. 103-111. · Zbl 0991.05041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.