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

DOI10.1007/S00373-022-02594-9MaRDI QIDQ2105863zbMATHOpenAlexFDO

Authors Morteza Hasanvand

Publication date 8 December 2022

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

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

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)

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.

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

Cites work

• Claw‐decompositions and tutte‐orientations
• Fast generation of planar graphs
• Fast generation of regular graphs and construction of cages
• Group chromatic number of planar graphs of girth at least 4
• 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
• Mod (2p + 1)-Orientations and $K_{1,2p+1}$-Decompositions
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On the degrees of the vertices of a directed graph
• Random 4-regular graphs have 3-star decompositions asymptotically almost surely
• Spanning trees and spanning Eulerian subgraphs with small degrees
• The weak 3-flow conjecture and the weak circular flow conjecture
• plantri

Cited in

(2)

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

Describes a project that uses

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)