@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.}
}

{"_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,\n title = {The Chromatic Index of Proper Circular-arc Graphs of\n Odd Maximum Degree which are Chordal},\n journal = {Electronic Notes in Theoretical Computer Science},\n volume = {346},\n pages = {125-133},\n year = {2019},\n note = {The proceedings of Lagos 2019, the tenth Latin and\n American Algorithms, Graphs and Optimization Symposium\n (LAGOS 2019)},\n _keywords = {Universal2016},\n organization = {UFMG},\n issn = {1571-0661},\n doi = {https://doi.org/10.1016/j.entcs.2019.08.012},\n url =\n {http://www.sciencedirect.com/science/article/pii/S1571066119300623},\n author = {João Pedro W. Bernardi and Murilo V. G. da Silva and\n André Luiz P. Guedes and Leandro M. Zatesko},\n keywords = {Pullback, circular-arc, chromatic index,\n edge-coloring, chordal},\n abstract = {The complexity of the edge-coloring problem when\n restricted to chordal graphs, listed in the famous\n D. Johnson's NP-completeness column of 1985, is still\n undetermined. A conjecture of Figueiredo, Meidanis,\n and Mello, open since the late 1990s, states that all\n chordal graphs of odd maximum degree Δ have chromatic\n index equal to Δ. This conjecture has already been\n proved for proper interval graphs (a subclass of\n proper circular-arc ∩ chordal graphs) of odd Δ by a\n technique called pullback. Using a new technique\n called multi-pullback, we show that this conjecture\n holds for all proper circular-arc ∩ chordal graphs of\n odd Δ. We also believe that this technique can be used\n for further results on edge-coloring other graph\n 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/andre/bibtex/meus.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"]}