Premium
Ramsey theory for graph connectivity
Author(s) -
Matula David W.
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070113
Subject(s) - combinatorics , monochromatic color , mathematics , ramsey's theorem , vertex (graph theory) , graph , vertex connectivity , integer (computer science) , discrete mathematics , physics , computer science , optics , programming language
r c ( k ) Denotes the smallest integer such that any c ‐edge‐coloring of the r c ( k ) vertex complete graph has a monochromatic k ‐connected subgraph. For any c, k ≧ 2, we show 2 c ( k – 1) + 1 ≦ r c ( k ) < 10/3 c ( k – 1) + 1, and further that 4( k – 1) + 1 ≧ r 2 ( k ) < (3 + √ ( k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.