Edge-colouring of triangle-free graphs with no proper majors

• Leandro M. Zatesko UFPR / UFFS
• Renato Carmo UFPR
• André Luiz P. Guedes UFPR

DOI: https://doi.org/10.5753/etc.2017.3181

Resumo

The problem of determining the chromatic index of a graph, even when triangle-free, is NP-hard. However, the Overfull Conjecture implies that this problem can be solved in polynomial time for graphs with large maximum degree. In order to prove the conjecture, it is sufficient to show that all nonsubgraph-overfull graphs with Δ > n/3 are Class 1. A special case of non-subgraph-overfull graphs are the graphs with no proper majors. We show that all triangle-free graphs with no proper majors, regardless of maximum degree, are Class 1. We also provide a polynomial-time algorithm to colour such graphs.

Referências

Hilton, A. J. W. and Johnson, P. D. (1987). Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Cambridge Philos. Soc., 102:103–112.

Holyer, I. (1981). The NP-completeness of edge-colouring. SIAM J. Comput., 10(4):718–720.

Koreas, D. P. (1997). The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3. J. Appl. Math. Comput., 93:13–17.

Niessen, T. (1994). How to find overfull subgraphs in graphs with large maximum degree. Discrete Appl. Math., 51:117–125.

Niessen, T. (2001). How to find overfull subgraphs in graphs with large maximum degree, II. Electron. J. Combin., 8.

Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz., 3:25–30. In Russian.

Zorzi, A. and Zatesko, L. M. (2016). On the chromatic index of join graphs and trianglefree graphs with large maximum degree. Discrete Appl. Math. Article in press: DOI: 10.1016/j.dam.2016.10.022.