𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cohomomorphisms of graphs and hypergraphs

✍ Scribed by Pavol Hell; Jaroslav Nešetřil

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
547 KB
Volume
87
Category
Article
ISSN
0025-584X

No coin nor oath required. For personal study only.

✦ Synopsis

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 to study the cohomomorphisms X -Y to find out more about the homomorphisms X --c Y .

In fact, it turns out that, at least for graphs, there is a close relationship between the two kinds of mappings, and that the cohomomorphisms are often easier to handle.

  1. Although we are interested mostly in graphs, in order to exhibit the dual character of homomorphisms and cohomomorphisms, it is convenient to consider graphs as a subclass of hypergraphs and describe the situation for hypergraphs in general. A hypergraph is an ordered pair ( V , E ) (also denoted by ( V ( X ) ,

E(X))

for the hypergraph X ) , where V is a set and E is a subset of the power-set of V . The elements of V are called vertices, the elements of E hyperedges. A hyperedge consisting of 2 vertices is called an edge, a hyperedge formed by 1 vertex a loop, and if 0 is a hyperedge, it is called the null-edge. A graph is a hypergraph every hyperedge of which is an edge or a loop. For a hypergraph X = ( V , E ) we shall often write X instead of V .

📜 SIMILAR VOLUMES

Indecomposable regular graphs and hyperg
Indecomposable regular graphs and hypergraphs
✍ Zoltán Füredi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 390 KB

Ftiredi, Z&an, Indecomposable regular graphs and hypergraphs, Discrete Mathematics 101 (1992) 59-64. Let G be a d-regular simple graph with n vertices. Here it is proved that for d > 6 -1, G contains a proper regular spanning subhypergraph. The same statement is proved for multigraphs with d > (n -1

Graph properties and hypergraph colourin
Graph properties and hypergraph colourings
✍ Jason I. Brown; Derek G. Corneil 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 855 KB

Given a graph property P, graph G and integer k 20, a P k-colouring of G is a function Jr:V(G)+ (1,. . ) k} such that the subgraph induced by each colour class has property P. When P is closed under induced subgraphs, we can construct a hypergraph HG such that G is P k-colourable iff Hg is k-colou

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

Chromatic numbers of hypergraphs and cov
Chromatic numbers of hypergraphs and coverings of graphs
✍ Zevi Miller; Heinrich Müller 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

Burr recently proved [3] that for positive integers m , , m 2 , . . , , m, and any graph G we have x(G) 5 &, if and only if G can be expressed as the edge disjoint union of subgraphs F, satisfying x(F,) 5 m,. This theorem is generalized to hypergraphs. By suitable interpretations the generalization