How to Find Overfull Subgraphs in Graphs with Large Maximum Degree, II

Abstract

Let $G$ be a simple graph with $3\Delta (G) > |V|$. The Overfull Graph Conjecture states that the chromatic index of $G$ is equal to $\Delta (G)$, if $G$ does not contain an induced overfull subgraph $H$ with $\Delta (H) = \Delta (G)$, and otherwise it is equal to $\Delta (G) +1$. We present an algorithm that determines these subgraphs in $O(n^{5/3}m)$ time, in general, and in $O(n^3)$ time, if $G$ is regular. Moreover, it is shown that $G$ can have at most three of these subgraphs. If $2\Delta (G) \geq |V|$, then $G$ contains at most one of these subgraphs, and our former algorithm for this situation is improved to run in linear time.