𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decompositions for the edge colouring of reduced indifference graphs

✍ Scribed by Celina M.H. de Figueiredo; João Meidanis; Célia Picinin de Mello; Carmen Ortiz

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
140 KB
Volume
297
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 positive evidence for the conjecture: every non neighbourhood-overfull indifference graph can be edge coloured with maximum degree colours. Two adjacent vertices are twins if they belong to the same maximal cliques. A graph is reduced if it contains no pair of twin vertices. A graph is overfull if the total number of edges is greater than the product of the maximum degree by n=2 , where n is the number of vertices. We give a structural characterization for neighbourhood-overfull indi erence graphs proving that a reduced indi erence graph cannot be neighbourhood-overfull. We show that the chromatic index for all reduced indi erence graphs is the maximum degree. We present two decomposition methods for edge colouring reduced indi erence graphs with maximum degree colours.

📜 SIMILAR VOLUMES

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+

A list version of Dirac's theorem on the
A list version of Dirac's theorem on the number of edges in colour-critical graphs
✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o

Optimal Ear Decompositions of Matching C
Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 225 KB

A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph G, b(G) denotes the number of bricks of G, and p(G) denotes the number of Petersen bricks of G. An ear decomposition of G is optimal if, among all ear decompositions of G, it u

An algorithm for the decomposition of gr
An algorithm for the decomposition of graphs into cliques
✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract Chung (F. R. K. Chung, On the decomposition of graphs, __SIAM J. Algebraic Discrete Methods__ 23 (1981), 1–12.) and independently Györi and Kostochka (E. Györi and A. V. Kostochka, On a problem of G. O. H. Katona and T. Tarján, __Acta Math. Acad. Sci. Hung.__ 34 (1979), 321–327.) proved

Computational algorithms for matching po
Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs
✍ Haruo Hosoya; K. Balasubramanian 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 736 KB

Computational algorithms are described which provide for constructing the set of associated edgeweighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or pur