Vol. 55, No. 1, 1974

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
 
Other MSP Journals
Ramsey theory and chromatic numbers

Gary Theodore Chartrand and Albert David Polimeni

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

Let χ(G) denote the chromatic number of a graph G. For positive integers n1,n2,,nk(k 1) the chromatic Ramsey number χ(n1,n2,,nk) is defined as the least positive integer p such that for any factorization Kp = i1kGi(Gi) ni for at least one i,1 i k. It is shown that χ(n1,n2,,nk) = 1 + i=1k(nt 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 n1,n2,,nk(k 1) the vertex-arboricity Ramsey number a(n1,n2,,nk) is defined as the least positive integer p such that for any factorization Kp = i=1kGi,a(Gi) ni for at least one i,1 i k. It is shown that a(n1,n2,,nk) = 1 + 2kΠi=1k(ni 1).

Mathematical Subject Classification 2000
Primary: 05C15
Milestones
Received: 4 October 1974
Published: 1 November 1974
Authors
Gary Theodore Chartrand
Albert David Polimeni