|  |
| Titel:
|
Claw-decompositions and Tutte-orientations |
| Type:
|
Journal articleJournal article |
| Person(er):
|
Forfatter:
Barat, Janos
Technical University of Denmark
Technical University of Denmark
Email:
|
| Uddrag:
|
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 \EG)\, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T=K-1,K-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[ log n]-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. (C) 2006 Wiley Periodicals, Inc. |
| Publiceret:
|
in journal: Journal of Graph Theory (ISSN: 0364-9024) (DOI: http://dx.doi.org/10.2002/jgt.20149), vol: 52, issue: 2, pages: 135-146, 2006 |
| DOI:
|
|
|
|