๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Graph properties and hypergraph colourings

โœ Scribed by Jason I. Brown; Derek G. Corneil

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
855 KB
Volume
98
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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-colourable. This correlation enables us to derive interesting new results in hypergraph chromatic theory from a 'graphic' approach.

In particular, we build vertex critical hypergraphs that are not edge critical, construct uniquely colourable hypergraphs with few edges and find graph-to-hypergraph transformations that preserve chromatic numbers.

๐Ÿ“œ SIMILAR VOLUMES

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

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

Median graphs and Helly hypergraphs
Median graphs and Helly hypergraphs
โœ H.M. Mulder; A. Schrijver ๐Ÿ“‚ Article ๐Ÿ“… 1979 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 963 KB
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