Ramsey theory and chromatic numbers

Gary Theodore Chartrand and Albert David Polimeni

Vol. 55 (1974), No. 1, 39–43

DOI: 10.2140/pjm.1974.55.39

Abstract

Let χ(G) denote the chromatic number of a graph G. For positive integers n₁,n₂,⋯,n_k(k ≧ 1) the chromatic Ramsey number χ(n₁,n₂,⋯,n_k) is defined as the least positive integer p such that for any factorization K_p = ⋃ _i⇒1^kG_i,χ(G_i) ≧ n_i for at least one i,1 ≦ i ≦ k. It is shown that χ(n₁,n₂,⋯,n_k) = 1 + ∏ _i=1^k(n_t − 1). The vertex-arboricity a(G) of a graph G is the fewest number of subsets into which the vertex set of G can be partitioned so that each subset induces an acyclic graph. For positive integers n₁,n₂,⋯,n_k(k ≧ 1) the vertex-arboricity Ramsey number a(n₁,n₂,⋯,n_k) is defined as the least positive integer p such that for any factorization K_p = ⋃ _i=1^kG_i,a(G_i) ≧ n_i for at least one i,1 ≦ i ≦ k. It is shown that a(n₁,n₂,⋯,n_k) = 1 + 2kΠ_i=1^k(n_i − 1).

Mathematical Subject Classification 2000

Primary: 05C15

Milestones

Received: 4 October 1974

Published: 1 November 1974