Coloring of Pseudocubic Graphs in Three Colors

Abstract

A graph is called pseudocubic if the degrees of all its vertices, with a single exception, do not exceed three, and the degree of an exceptional vertex does not exceed four. In this work, it is proved that the vertices of a pseudocubic graph without induced subgraphs that are isomorphic to K₄ or K₄⁻ can be colored in three colors. In addition, it is shown that the problem of 3-coloring of pseudocubic graphs can be solved using a polynomial algorithm.