Skip to main content
Article
On tripartite common graphs
arXiv
  • Andrzej Grzesik, Jagiellonian University
  • Joonkyung Lee, University College London
  • Bernard Lidicky, Iowa State University
  • Jan Volec, Czech Technical University
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
12-3-2020
Abstract

A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture.

Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.

Comments

This preprint is made available through arXiv: https://arxiv.org/abs/2012.02057.

Creative Commons License
Creative Commons Attribution 4.0 International
Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Andrzej Grzesik, Joonkyung Lee, Bernard Lidicky and Jan Volec. "On tripartite common graphs" arXiv (2020)
Available at: http://works.bepress.com/bernard-lidicky/67/