The existence of planar $4$-connected essentially $6$-edge-connected graphs with no claw-decompositions

Abstract

In 2006 Bar{á}t and Thomassen conjectured that every planar $4$-edge-connected $4$-regular simple graph of size divisible by three admits a claw-decomposition. Later, Lai (2007) disproved this conjecture by a family of planar graphs with edge-connectivity $4$ which the smallest one contains $24$ vertices. In this note, we first give a smaller counterexample having only $18$ vertices and next construct a family of planar $4$-connected essentially $6$-edge-connected $4$-regular simple graphs of size divisible by three with no claw-decompositions. This result provides the sharpness for two known results which say that every $5$-edge-connected graph of size divisible by three admits a claw-decomposition if it is essentially $6$-edge-connected or planar.

This paper is an improved version of a removed part of the paper arXiv:1702.07039