Decomposing a graph into bistars

Carsten Thomassen

doi:10.1016/j.jctb.2013.05.003

Decomposing a graph into bistars

Carsten Thomassen

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

Bárat and the present author conjectured 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 G has a T-decomposition, that is, a decomposition of the edge set into trees each of which is isomorphic to T. The conjecture has been verified for infinitely many paths and for each star. In this paper we verify the conjecture for an infinite family of trees that are neither paths nor stars, namely all the bistars S(k,k+1).

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	103
Issue number	4
Pages (from-to)	504-508
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2013.05.003
Publication status	Published - 2013

Keywords

Orientations modulo k
Bistar decomposition
3-Flow conjecture

Access to Document

10.1016/j.jctb.2013.05.003

OpenUrl availability

Full text

Cite this

@article{7c9b57b7e5b54969892f4b49bdaa7616,

title = "Decomposing a graph into bistars",

abstract = "B{\'a}rat and the present author conjectured that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT-edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition, that is, a decomposition of the edge set into trees each of which is isomorphic to T. The conjecture has been verified for infinitely many paths and for each star. In this paper we verify the conjecture for an infinite family of trees that are neither paths nor stars, namely all the bistars S(k,k+1).",

keywords = "Orientations modulo k, Bistar decomposition, 3-Flow conjecture",

author = "Carsten Thomassen",

year = "2013",

doi = "10.1016/j.jctb.2013.05.003",

language = "English",

volume = "103",

pages = "504--508",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "4",

}

TY - JOUR

T1 - Decomposing a graph into bistars

AU - Thomassen, Carsten

PY - 2013

Y1 - 2013

N2 - Bárat and the present author conjectured that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT-edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition, that is, a decomposition of the edge set into trees each of which is isomorphic to T. The conjecture has been verified for infinitely many paths and for each star. In this paper we verify the conjecture for an infinite family of trees that are neither paths nor stars, namely all the bistars S(k,k+1).

AB - Bárat and the present author conjectured that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT-edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition, that is, a decomposition of the edge set into trees each of which is isomorphic to T. The conjecture has been verified for infinitely many paths and for each star. In this paper we verify the conjecture for an infinite family of trees that are neither paths nor stars, namely all the bistars S(k,k+1).

KW - Orientations modulo k

KW - Bistar decomposition

KW - 3-Flow conjecture

U2 - 10.1016/j.jctb.2013.05.003

DO - 10.1016/j.jctb.2013.05.003

M3 - Journal article

SN - 0095-8956

VL - 103

SP - 504

EP - 508

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 4

ER -

Decomposing a graph into bistars

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this