On the chromatic index of complementary prisms

Abstract

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.