Ramseyan properties of graphs (Q1379170)
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 1120240
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Ramseyan properties of graphs |
scientific article; zbMATH DE number 1120240 |
Statements
Ramseyan properties of graphs (English)
0 references
22 February 1998
0 references
Summary: Every graph of chromatic number \(k\) with more than \(k(r-1)(b-1)\) vertices has a \(b\)-element independent set of vertices such that if any two of them are joined by an edge then the chromatic number stays the same or an \(r\)-element independent set of vertices such that joining any two of them by an edge increases the chromatic number.
0 references
Ramsey graph
0 references
chromatic number
0 references
independent set
0 references
0.765066921710968
0 references
