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).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

{"_id":"KXWmQxet75SFP3t3K","bibbaseid":"bernardi-dasilva-guedes-zatesko-thechromaticindexofpropercirculararcgraphsofoddmaximumdegreewhicharechordal-2019","authorIDs":["5aDCEbTc8DEcmwPjP","5e3b3421255dcade01000116","5e446969084293df0100006c","5e4486d6ec14b3de01000083","5e46f963461d04f201000119","5e4e91ca9b7bbade01000156","5e4e951f9b7bbade010001d8","5e4ea40964b624de010000c8","5e4ed2722962cadf01000030","5e551b440096f9de0100007f","5e62a99208ebcade01000150","5e659ca25dd5c8de01000097","96kL4gCBP5FoqsRas","J2C57oh33kb32dCxz","bGjvG4AKHiX2cc7YG","fDLzHgeeX2HLGn9dM","m46QHpvf79WSptWRW","nhK8gHPJzMitxAzQ6","rZYT5zZRnwSxoFJa9","sJqxjCtsgbZxh8Zrk","xjLgNamFKzfeoqvdv"],"author_short":["Bernardi, J. P. W.","da Silva, M. V. G.","Guedes, A. L. P.","Zatesko, L. M."],"bibdata":{"bibtype":"article","type":"article","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":[{"firstnames":["João","Pedro","W."],"propositions":[],"lastnames":["Bernardi"],"suffixes":[]},{"firstnames":["Murilo","V.","G."],"propositions":["da"],"lastnames":["Silva"],"suffixes":[]},{"firstnames":["André","Luiz","P."],"propositions":[],"lastnames":["Guedes"],"suffixes":[]},{"firstnames":["Leandro","M."],"propositions":[],"lastnames":["Zatesko"],"suffixes":[]}],"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.","bibtex":"@article{Bernardi2019,\ntitle = \"The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal\",\njournal = \"Electronic Notes in Theoretical Computer Science\",\nvolume = \"346\",\npages = \"125 - 133\",\nyear = \"2019\",\nnote = \"The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).\",\n _keywords = {Universal2016},\norganization={UFMG},\nissn = \"1571-0661\",\ndoi = \"https://doi.org/10.1016/j.entcs.2019.08.012\",\nurl = \"http://www.sciencedirect.com/science/article/pii/S1571066119300623\",\nauthor = \"João Pedro W. Bernardi and Murilo V. G. da Silva and André Luiz P. Guedes and Leandro M. Zatesko\",\nkeywords = \"Pullback, circular-arc, chromatic index, edge-coloring, chordal\",\nabstract = \"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.\"\n}\n\n","author_short":["Bernardi, J. P. W.","da Silva, M. V. G.","Guedes, A. L. P.","Zatesko, L. M."],"key":"Bernardi2019","id":"Bernardi2019","bibbaseid":"bernardi-dasilva-guedes-zatesko-thechromaticindexofpropercirculararcgraphsofoddmaximumdegreewhicharechordal-2019","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S1571066119300623"},"keyword":["Pullback","circular-arc","chromatic index","edge-coloring","chordal"],"metadata":{"authorlinks":{"guedes, a":"https://www.inf.ufpr.br/andre/producao.html"}},"downloads":0},"bibtype":"article","biburl":"http://www.inf.ufpr.br/teoria/universal2016/universal.bib","creationDate":"2020-02-05T21:31:26.255Z","downloads":0,"keywords":["pullback","circular-arc","chromatic index","edge-coloring","chordal"],"search_terms":["chromatic","index","proper","circular","arc","graphs","odd","maximum","degree","chordal","bernardi","da silva","guedes","zatesko"],"title":"The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal","year":2019,"dataSources":["wKyTDzPCLmTgMwZxK","8EF7A9sBtzR7yAc4T"]}