On the chromatic index of complementary prisms

Main Article Content

Leandro Miranda Zatesko Renato Carmo André L. P. Guedes Alesom Zorzi Raphael C. S. Machado Celina M. H. Figueiredo


This paper addresses the edge-colouring problem restricted to the graph class of complementary prisms. This graph class includes the Petersen graph, a very important and widely studied graph in the context of graph edge-colouring and remarkable related open questions, such as the Overfull Conjecture. We prove that all non-regular complementary prisms are Class 1 and we conjecture that the only Class 2 regular complementary prism is the Petersen graph. We present evidences for this conjecture.

Article Details

How to Cite
Zatesko, L., Carmo, R., Guedes, A., Zorzi, A., Machado, R., & Figueiredo, C. (2019). On the chromatic index of complementary prisms. Acta Mathematica Universitatis Comenianae, 88(3), 1071-1077. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1208/764