𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the orientation of graphs and hypergraphs

✍ Scribed by András Frank; Tamás Király; Zoltán Király

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
198 KB
Volume
131
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Graph orientation is a well-studied area of combinatorial optimization, one that provides a link between directed and undirected graphs. An important class of questions that arise in this area concerns orientations with connectivity requirements. In this paper we focus on how similar questions can be asked about hypergraphs, and we show that often the answers are also similar: many known graph orientation theorems can be extended to hypergraphs, using the familiar uncrossing techniques. Our results also include a short proof and an extension of a theorem of Khanna et al.

📜 SIMILAR VOLUMES

On splittable colorings of graphs and hy
On splittable colorings of graphs and hypergraphs
✍ Zoltán Füredi; Radhika Ramamurthi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## 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

Cohomomorphisms of graphs and hypergraph
Cohomomorphisms of graphs and hypergraphs
✍ Pavol Hell; Jaroslav Nešetřil 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 547 KB

In addition to a widely studied notion of homomorphisms of graphs and hypergraphs, [2, 5 , 6, 7, 9, 13, 141, we introduce the dual notion of cohomomorphisms. We shall concentrate on only a few aapects of these mappings, mostly with regard to intended applications, [lo, 111. Our basic motivation is t

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 the orientation of meyniel graphs
On the orientation of meyniel graphs
✍ Mostaffa Blidia; Pierre Duchet; Frédéric Maffray 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

## Abstract A kernel of a directed graph is a set of vertices __K__ that is both absorbant and independent (i.e., every vertex not in __K__ is the origin of an arc whose extremity is in __K__, and no arc of the graph has both endpoints in __K__). In 1983, Meyniel conjectured that any perfect graph,

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