Premium
On splittable colorings of graphs and hypergraphs
Author(s) -
Füredi Zoltán,
Ramamurthi Radhika
Publication year - 2002
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.10044
Subject(s) - mathematics , combinatorics , greedy coloring , graph coloring , generalization , ramsey theory , discrete mathematics , list coloring , graph , edge coloring , line graph , graph power , mathematical analysis
Abstract The notion of a split coloring of a complete graph was introduced by Erdős and Gyárfás [7] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal ( r , m )‐split coloring problem of [7] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002