𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic number of finite and infinite graphs and hypergraphs

✍ Scribed by Paul Erdös; Andras Hajnal

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
349 KB
Volume
53
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We wrote many papers on these subjects, some in collaboration with Galvin, Rado, Shelah and Szemer6di, and posed many problems some of which turned out to be undecidable. In this survey we state some old and new solved and unsolved problems.

Nous avons 6crit beaucoup d'articles, certains en collaboration avec Galvin, Rado, Shelah et Szemer6di, au sujet du hombre chromatique des graphes et des hypergraphes, finis ou infinis. Nous avons pos6 bien des probl~mes, dont certains se sont av6r6s ind6cidables. Darts cette br~ve synth~se nous pr6sentons quelques probl~mes, anciens ou r6cents, r6solus ou encore en suspens.

📜 SIMILAR VOLUMES

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

The fractional chromatic number of infin
The fractional chromatic number of infinite graphs
✍ Imre Leader 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 398 KB 👁 1 views

## Abstract The fractional chromatic number of a graph __G__ is the infimum of the total weight that can be assigned to the independent sets of __G__ in such a way that, for each vertex __v__ of __G__, the sum of the weights of the independent sets containing __v__ is at least 1. In this note we g

Oriented hypergraphs, stability numbers
Oriented hypergraphs, stability numbers and chromatic numbers
✍ Heinrich Müller 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Oriented hypergraphs are defined, so that it is possible to genc&ze popositions characterizing the chromatic number and the stability number of a graph by means of crientations i!tnd elementary paths, to the strong and weak chromatic number and the strong and we& stability number of a hypergraph.

Circular Chromatic Numbers and Fractiona
Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs
✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

Regular graphs and edge chromatic number
Regular graphs and edge chromatic number
✍ R.J Faudree; J Sheehan 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 376 KB

For any simple graph G, Vizing's Theorem [5] implies that A (G)~)((G)<~ A(G)+ 1, where A (G) is the maximum degree of a vertex in G and x(G) is the edge chromatic number. It is of course possible to add edges to G without changing its edge chromatic number. Any graph G is a spanning subgraph of an e

Edge-face chromatic number and edge chro
Edge-face chromatic number and edge chromatic number of simple plane graphs
✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) →  {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_