Premium
Claw‐decompositions and tutte‐orientations
Author(s) -
Barát János,
Thomassen Carsten
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20149
Subject(s) - combinatorics , mathematics , vertex (graph theory) , claw , conjecture , graph , discrete mathematics , mechanical engineering , engineering
Abstract We conjecture that, for each tree T , there exists a natural number k T such that the following holds: If G is a k T ‐edge‐connected graph such that | E ( T )| divides | E ( G )|, then the edges of G can be divided into parts, each of which is isomorphic to T . We prove that for T = K 1,3 (the claw), this holds if and only if there exists a (smallest) natural number k t such that every k t ‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006