𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizing and edge-colouring split-indifference graphs

✍ Scribed by Z. Carmen Ortiz; Nelson Maculan; Jayme L. Szwarcfiter

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
540 KB
Volume
82
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 which all its edges have different colours. Based on the two results, WC obtain equations for computing the chromatic index of graphs of the considered class, in linear time. We recall that the chromatic index problem is still unsolved for both classes of split and indifference graphs. I? 19% Elsc\icr Science B.V. All rights reserved.

πŸ“œ SIMILAR VOLUMES

On edge-colouring indifference graphs
On edge-colouring indifference graphs
✍ Celina M.H. de Figueiredo; JoΓ£o Meidanis; CΓ©lia Picinin de Mello πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 1020 KB
Decompositions for the edge colouring of
Decompositions for the edge colouring of reduced indifference graphs
✍ Celina M.H. de Figueiredo; JoΓ£o Meidanis; CΓ©lia Picinin de Mello; Carmen Ortiz πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 140 KB

The chromatic index problem-ΓΏnding the minimum number of colours required for colouring the edges of a graph-is still unsolved for indi erence graphs, whose vertices can be linearly ordered so that the vertices contained in the same maximal clique are consecutive in this order. We present new positi

On characterizing Vizing's edge colourin
On characterizing Vizing's edge colouring bound
✍ Penny Haxell; Jessica McDonald πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 98 KB

**Features recent advances and new applications in graph edge coloring**Reviewing recent advances in the Edge Coloring Problem, __Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture__ provides an overview of the current state of the science, explaining the interconnections among the resu

Simultaneously Colouring the Edges and F
Simultaneously Colouring the Edges and Faces of Plane Graphs
✍ Adrian O. Waller πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 345 KB

In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured with 2+