scientific article; zbMATH DE number 1743977
A property of graphs is an isomorphism-closed subclass of the class of all finite simple graphs. Let \(G\) be a graph, \(e\) be an edge of the complement of \(G\) and \(\mathcal P\) be a graph property. The edge \(e\) is coloured blue if \(G+e\) belongs to \(\mathcal P\) and red otherwise. A property \(\mathcal P\) of graphs is called Ramseyan if large graphs with the property \(\mathcal P\) have large monochromatic subgraphs. Let us denote by \(\mathcal T\) the class of connected and triangle-free graphs. Let \(T(r,b)\) be the smallest \(n\) such that every connected triangle-free graph of order at least \(n\) contains either an \(r\)-element red clique or \(b\)-element blue clique. It is shown that for \(b \geq 2\) and \(r\geq 3\) the inequality \(T(r,b)\leq (b-1)(r^2-2r)+3\) holds. The exact values of \(T(r,b)\) for small values of \(b\) and \(r\) are established as well. Therefore the property \(\mathcal T\) is Ramseyan. A lower bound and an improved general upper bound of \(T(r,b)\) is presented for \(b\geq 2\) and \(r=4\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4529454)
