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

DOI10.1007/S00373-022-02594-9zbMATH Open1504.05233arXiv2205.09063OpenAlexW4311624077MaRDI QIDQ2105863FDOQ2105863

Authors: Morteza Hasanvand 

Publication date: 8 December 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: In 2006 Bar{'a}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.

Full work available at URL: https://arxiv.org/abs/2205.09063

Recommendations

• Mod (2p + 1)-Orientations and $K_{1,2p+1}$-Decompositions
• Claw‐decompositions and tutte‐orientations
• Structure of 4-connected claw-free graphs not containing a subdivision of \(K_{5}\)
• \(Z_3\)-connectivity of claw-free graphs
• Claw-free graphs. IV: Decomposition theorem

zbMATH Keywords

planar graphmodulo orientationedge-connectivityclaw-decompositionstar-decomposition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• plantri
• Fast generation of regular graphs and construction of cages
• On the degrees of the vertices of a directed graph
• Fast generation of planar graphs
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Group-colouring, group-connectivity, claw-decompositions, and orientations in 5-edge-connected planar graphs
• The weak 3-flow conjecture and the weak circular flow conjecture
• Claw‐decompositions and tutte‐orientations
• Spanning trees and spanning Eulerian subgraphs with small degrees
• Group chromatic number of planar graphs of girth at least 4
• Mod (2p + 1)-Orientations and $K_{1,2p+1}$-Decompositions
• Random 4-regular graphs have 3-star decompositions asymptotically almost surely

Cited In (2)

• Modulo orientations with bounded out-degrees
• Mod (2p + 1)-Orientations and $K_{1,2p+1}$-Decompositions

Uses Software

• plantri
• GENREG

This page was built for publication: The existence of planar 4-connected essentially 6-edge-connected graphs with no claw-decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105863)