✦ LIBER ✦

Recent progress on edge-colouring graphs

✍ Scribed by A.J.W Hilton

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 315 KB
Volume: 64
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90200-7

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we summarize some of the progress made recently by the author, A.G. Chetwynd and P.D. Johnson about edge-eolourings of graphs with relatively large maximum degree.

In this note, multigraphs will have no loops. For a multigraph G, the least number of colours needed to colour the edges of G in such a way that no two edges on the same vertex of G have the same colour, is called the edge-chromatic number,

, then G is said to be Class 1, and otherwise G is Class 2. If G is a simple graph, then Vizing showed that x'(G) ~< A(G) + 1.

📜 SIMILAR VOLUMES

Edge-colouring random graphs

✍ A.M Frieze; B Jackson; C.J.H McDiarmid; B Reed 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 653 KB

Edge colouring line graphs of unicyclic

Edge colouring line graphs of unicyclic graphs

✍ Leizhen Cai; John A. Ellis 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 691 KB

Characterizing and edge-colouring split-

Characterizing and edge-colouring split-indifference graphs

✍ Z. Carmen Ortiz; Nelson Maculan; Jayme L. Szwarcfiter 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 540 KB

We describe a simple characterization of graphs which are simultaneouly split and mdiffcrcncc graphs. In the sequel, WE present a method for optimally edge colouring a complete graph M ith an c\en number > 6 of vertices, leading to a simple construction for exhibiting a perfect matching of it. in wh

NP-completeness of edge-colouring some r

NP-completeness of edge-colouring some restricted graphs

✍ Leizhen Cai; John A. Ellis 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 850 KB

Two conjectures on edge-colouring

✍ A.J.W. Hilton 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 311 KB

## Chetwynd and Hilton have elsewhere posed two conjectures, one a general statement on edge-colouring simple graphs G with A(G) > i lV(G)I, and a second to the effect that a regular simple graph G with d(G) 3 -1 IV(G) 1 is l-factorizable. We set out the evidence for both these conjectures and sho

Transformations of edge-coloured cubic g

Transformations of edge-coloured cubic graphs

✍ Yasuyuki Tsukui 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 491 KB

For a simple 3-edge-coloured cubic graph, an edge-c-reduction and three transformations (S-, X-, and H-transformation) are defined. Each transformation preserves order and regularity of graphs. They also define metrics on the set of all (connected) 3-edge-coloured cubic graphs with the same order. A