𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On splittable colorings of graphs and hypergraphs

✍ Scribed by Zoltán Füredi; Radhika Ramamurthi

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
109 KB
Volume
40
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Coloring Face-Hypergraphs of Graphs on S
Coloring Face-Hypergraphs of Graphs on Surfaces
✍ André Kündgen; Radhika Ramamurthi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 223 KB

The face-hypergraph, H(G), of a graph G embedded in a surface has vertex set V(G), and every face of G corresponds to an edge of H(G) consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs. A hypergraph is k-colorable (k-choosable) if there is a c

On Total Colorings of Graphs
On Total Colorings of Graphs
✍ C. Mcdiarmid; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 299 KB

AND Bruce Reed Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada

Investigation on Interval Edge-Colorings
Investigation on Interval Edge-Colorings of Graphs
✍ A.S. Asratian; R.R. Kamalian 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 380 KB

An edge-coloring of a simple graph \(G\) with colors \(1,2, \ldots, t\) is called an interval \(t\)-coloring [3] if at least one edge of \(G\) is colored by color \(i, i=1, \ldots, t\) and the edges incident with each vertex \(x\) are colored by \(d_{G}(x)\) consecutive colors, where \(d_{G}(x)\) is

Neighborhood hypergraphs of bipartite gr
Neighborhood hypergraphs of bipartite graphs
✍ Endre Boros; Vladimir Gurvich; Igor Zverovich 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

## Abstract Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the litera

On line graphs of linear 3-uniform hyper
On line graphs of linear 3-uniform hypergraphs
✍ Metelsky, Yury; Tyshkevich, Regina 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

It is known that the class of line graphs of linear 3-uniform hypergraphs cannot be characterized by a finite list of forbidden induced subgraphs (R. N.