On Ramsey theory and graphical parameters

Linda M. Lesniak and John A. Roberts

Vol. 68 (1977), No. 1, 105–114

DOI: 10.2140/pjm.1977.68.105

Abstract

A graph G is said to have a factorization into the subgraphs G₁,⋯,G_k if the subgraphs are spanning, pairwise edge-disjoint, and the union of their edge sets equals the edge set of G. For a graphical parameter f and positive integers n₁,n₂,⋯,n_k(k ≧ 1), the f-Ramsey number f(n₁,n₂,⋯,n_k) is the least positive integer p such that for any factorization K_p = ⋃ _I^k = 1G₁, it follows that f(G,) ≧ n, for at least one i, 1 ≦ i ≦ k. In the following, we present two results involving f-Ramsey numbers which hold for various vertex and edge partition parameters, respectively. It is then shown that the concept of f-Ramsey number can be generalized to more than one vertex partition parameter, more than one edge partition parameter, and combinations of vertex and edge partition parameters. Formulas are presented for these generalized f-Ramsey numbers and specific illustrations are given.

Mathematical Subject Classification 2000

Primary: 05C35

Milestones

Received: 9 June 1975

Revised: 23 July 1976

Published: 1 January 1977