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

被引：0

作者：

Bernardi, Joao Pedro W. ^{[1
]}

da Silva, Murilo V. G. ^{[1
]}

Guedes, Andre Luiz P. ^{[1
]}

Zatesko, Leandro M. ^{[1
,2
]}

机构：

[1] Univ Fed Parana, Dept Informat, Curitiba, Parana, Brazil

[2] Fed Univ Fronteira Sul, Chapeco, Brazil

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2019年 / 346卷

关键词：

Pullback; circular-arc; chromatic index; edge-coloring; chordal; NP-COMPLETENESS;

D O I：

10.1016/j.entcs.2019.08.012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 Delta have chromatic index equal to Delta. This conjecture has already been proved for proper interval graphs (a subclass of proper circular-arc boolean AND chordal graphs) of odd Delta by a technique called pullback. Using a new technique called multi-pullback, we show that this conjecture holds for all proper circular-arc boolean AND chordal graphs of odd Delta. We also believe that this technique can be used for further results on edge-coloring other graph classes.

引用

页码：125 / 133

页数：9