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

Corrigendum to: on graphs critical with respect to edge-colourings

โœ Scribed by H.P. Yap

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
37 KB
Volume
80
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

On graphs critical with respect to edge-colourings, Discrete Math. 37 (1981) 289-296. The error occurs in the proof of Case 2 of Theorem 5 (p. 294). We now revise the proof for Case 1 (p. 293) and Case 2 (p. 294) as follows:

Case 1: jI # p. In this case, the terminal vertex of the (1, p)-chain with initial vertex w, cannot contain y, or y. By interchanging the colours 1 and p in this chain we yield a contradiction to what we have proved above. Hence this case cannot occur.

Case 2: jr = p. Let Q be the (p, 2)-chain with initial vertex wr. If the terminal vertex of Q is X, then z r$ Q. By the Kempe-chain argument on Q, we get a contradiction. On the other hand, if the terminal vertex of Q is not x, then by interchanging the colours p and 2 in Q, we will go back to Case 1. 0

๐Ÿ“œ SIMILAR VOLUMES

On the Number of Edges in Hypergraphs Cr
On the Number of Edges in Hypergraphs Critical with Respect to Strong Colourings
โœ Alexandr V. Kostochka; Douglas R. Woodall ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 94 KB

A colouring of the vertices of a hypergraph G is called strong if, for every edge A, the colours of all vertices in A are distinct. It corresponds to a colouring of the generated graph (G) obtained from G by replacing every edge by a clique. We estimate the minimum number of edges possible in a k-cr

On graphs critical with respect to verte
On graphs critical with respect to vertex partition numbers
โœ Peter Mihรณk ๐Ÿ“‚ Article ๐Ÿ“… 1981 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 362 KB

For k 3 0, pk(G) den ot e s the Lick-White vertex partition number of G. A graph G is called (n, k)-critical 'f 't I I is connected and for each edge e of G Pk (G -e) < pk (G) = n. We describe all (2, k&critical graphs and for n 23, k 2 1 we extend and simplify a result of Bollobas and Harary giving

Definitions of criticality with respect
Definitions of criticality with respect to edge-coloring
โœ A. J. W. Helton ๐Ÿ“‚ Article ๐Ÿ“… 1977 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 310 KB

## Abstract Here we examine six definitions of criticality concerning the chromatic index (edge chromatic number) of a simple graph. Five of these turn out to be almost always almost equivalent. Some problems arise and some conjectures are posed.