No label defined (Q4529454)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1743977
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1743977

      Statements

      9 October 2002
      0 references
      Ramseyan property
      0 references
      triangle-free graphs
      0 references
      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\).
      0 references

      Identifiers