A conformabilidade dos grafos subcúbicos

Uma $k$-coloração de vértices de um grafo $G=(V,E)$ é uma atribuição de $k$ cores aos vértices de $G$, tal que vértices adjacentes têm cores diferentes. A deficiência de $G$ é $def(G)=\sum_{v \in V} (\Delta-d(v))$. Um grafo $G$ é conformable se $G$ possui uma $(\Delta+1)$-coloração de vértices em que o número de classes de cor (incluindo classes de cor vazias) com paridade diferente de $|V|$ é no máximo $def(G)$. Neste trabalho estabelecemos a classificação da classe dos grafos subcúbicos conformable. Provamos que um grafo $G$ é subcúbico não-conformable, se e somente se, $G$ é uma união disjunta entre um número ímpar de componentes de $K_4$, ou $G$ é uma união disjunta entre um número ímpar de componentes de $K_4$ com o prisma triangular, ou $G$ é uma união disjunta entre um número par de componentes de $K_4$ com o $K_{3,3}$. Nossa construção conduz a um algoritmo em tempo polinomial.