The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal. Bernardi, J. P. W., da Silva, M. V. G., Guedes, A. L. P., & Zatesko, L. M. Electronic Notes in Theoretical Computer Science, 346:125 - 133, 2019. The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).
The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal [link]Paper  doi  abstract   bibtex   
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.
@article{Bernardi2019,
title = "The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal",
journal = "Electronic Notes in Theoretical Computer Science",
volume = "346",
pages = "125 - 133",
year = "2019",
note = "The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).",
  _keywords =    {Universal2016},
organization={UFMG},
issn = "1571-0661",
doi = "https://doi.org/10.1016/j.entcs.2019.08.012",
url = "http://www.sciencedirect.com/science/article/pii/S1571066119300623",
author = "João Pedro W. Bernardi and Murilo V. G. da Silva and André Luiz P. Guedes and Leandro M. Zatesko",
keywords = "Pullback, circular-arc, chromatic index, edge-coloring, chordal",
abstract = "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."
}

Downloads: 0