The problem of path decomposition for graphs with treewidth at most 4

Changhong Lu; Niping Yi

doi:10.1016/j.disc.2024.113957

The problem of path decomposition for graphs with treewidth at most 4

Changhong Lu
, Niping Yi^*

^*Corresponding author for this work

School of Mathematical Sciences

East China Normal University

Research output: Contribution to journal › Article › peer-review

Abstract

Gallai conjectured that every connected graph with n vertices admits a decomposition into at most [Formula presented] paths. The conjecture has been proved for some special cases. Recently, Botler et al. (2020) proved that Gallai's conjecture holds for graphs with treewidth at most 3. In this paper, we show that if G is a graph with treewidth at most 4, then G can be decomposed into at most [Formula presented] paths or G is isomorphic to K₃, to K₅⁻(K₅−e), or to K₅.

Original language	English
Article number	113957
Journal	Discrete Mathematics
Volume	347
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2024.113957
State	Published - Jun 2024

Keywords

Gallai's conjecture
Path decomposition
Treewidth
k-tree

Access to Document

10.1016/j.disc.2024.113957

Cite this

@article{fd81f6dd3ba3491a9719501e1b52b674,

title = "The problem of path decomposition for graphs with treewidth at most 4",

abstract = "Gallai conjectured that every connected graph with n vertices admits a decomposition into at most [Formula presented] paths. The conjecture has been proved for some special cases. Recently, Botler et al. (2020) proved that Gallai's conjecture holds for graphs with treewidth at most 3. In this paper, we show that if G is a graph with treewidth at most 4, then G can be decomposed into at most [Formula presented] paths or G is isomorphic to K3, to K5−(K5−e), or to K5.",

keywords = "Gallai's conjecture, Path decomposition, Treewidth, k-tree",

author = "Changhong Lu and Niping Yi",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = jun,

doi = "10.1016/j.disc.2024.113957",

language = "英语",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - The problem of path decomposition for graphs with treewidth at most 4

AU - Lu, Changhong

AU - Yi, Niping

PY - 2024/6

Y1 - 2024/6

N2 - Gallai conjectured that every connected graph with n vertices admits a decomposition into at most [Formula presented] paths. The conjecture has been proved for some special cases. Recently, Botler et al. (2020) proved that Gallai's conjecture holds for graphs with treewidth at most 3. In this paper, we show that if G is a graph with treewidth at most 4, then G can be decomposed into at most [Formula presented] paths or G is isomorphic to K3, to K5−(K5−e), or to K5.

AB - Gallai conjectured that every connected graph with n vertices admits a decomposition into at most [Formula presented] paths. The conjecture has been proved for some special cases. Recently, Botler et al. (2020) proved that Gallai's conjecture holds for graphs with treewidth at most 3. In this paper, we show that if G is a graph with treewidth at most 4, then G can be decomposed into at most [Formula presented] paths or G is isomorphic to K3, to K5−(K5−e), or to K5.

KW - Gallai's conjecture

KW - Path decomposition

KW - Treewidth

KW - k-tree

UR - https://www.scopus.com/pages/publications/85187380242

U2 - 10.1016/j.disc.2024.113957

DO - 10.1016/j.disc.2024.113957

M3 - 文章

AN - SCOPUS:85187380242

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

M1 - 113957

ER -

The problem of path decomposition for graphs with treewidth at most 4

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this