Classificação de cografos quanto ao índice cromático

Abstract

Edge colouring, a problem which consists in figuring out how many colours are needed to provide a minimal colouring of the edges of a graph, is NP-complete (even though, according to Vizing’s Theorem, there are only two possibilities for the minimum number of colours). However, when dealing with some graph subclasses, it admits a polynomial or linear solution. For cograph class (graphs which do not have a P4 as an induced subgraph), this problem has not been solved yet. Nevertheless there are indications that it admits not only a polynomial solution but also a linear one, given the existence of the Overfull Conjecture and other results related to edge colouring of cograph subclasses. From this observation, we propose a conjecture, based on evidence drawn from a computer program specially designed for generation of cographs. The conjecture applies to the join operation when one of the operands has an acyclic core. In addition, we present two theorems for more restricted cases of the conjecture: when the acyclic core is edgeless and when there is a matching which does not cover the core of the other graph.