The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal

The complexity of the edge-coloring problem when restricted to chordal graphs, listed in the famous D. Johnson's NP-completeness column of 1985, is still undetermined. A conjecture of Figueiredo, Meidanis, and Mello, open since the late 1990s, states that all chordal graphs of odd maximum degre...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2019-08, Vol.346, p.125-133
Main Authors: Bernardi, João Pedro W., da Silva, Murilo V.G., Guedes, André Luiz P., Zatesko, Leandro M.
Format: Article
Language:English
Subjects:
chordal
chromatic index
circular-arc
edge-coloring
Pullback
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The complexity of the edge-coloring problem when restricted to chordal graphs, listed in the famous D. Johnson's NP-completeness column of 1985, is still undetermined. A conjecture of Figueiredo, Meidanis, and Mello, open since the late 1990s, states that all chordal graphs of odd maximum degree Δ have chromatic index equal to Δ. This conjecture has already been proved for proper interval graphs (a subclass of proper circular-arc ∩ chordal graphs) of odd Δ by a technique called pullback. Using a new technique called multi-pullback, we show that this conjecture holds for all proper circular-arc ∩ chordal graphs of odd Δ. We also believe that this technique can be used for further results on edge-coloring other graph classes.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2019.08.012