Gallai's path decomposition conjecture for graphs of small maximum degree

Marthe Bonamy; Thomas J. Perrett

doi:10.1016/j.disc.2019.01.005

Gallai's path decomposition conjecture for graphs of small maximum degree

Marthe Bonamy^*, Thomas J. Perrett

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Université de Bordeaux

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

100 Downloads (Pure)

Abstract

Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most [Formula presented] paths. We confirm that conjecture for all graphs with maximum degree at most five.

Original language	English
Journal	Discrete Mathematics
Volume	342
Issue number	5
Pages (from-to)	1293-1299
Number of pages	7
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2019.01.005
Publication status	Published - 2019

Keywords

05C70
Maximum degree
Path decomposition

Access to Document

10.1016/j.disc.2019.01.005

FulltextAccepted author manuscript, 170 KBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{d904dca3b6fa46578cdb64cbb69c8dde,

title = "Gallai's path decomposition conjecture for graphs of small maximum degree",

abstract = "Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most [Formula presented] paths. We confirm that conjecture for all graphs with maximum degree at most five.",

keywords = "05C70, Maximum degree, Path decomposition",

author = "Marthe Bonamy and Perrett, {Thomas J.}",

year = "2019",

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

language = "English",

volume = "342",

pages = "1293--1299",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Gallai's path decomposition conjecture for graphs of small maximum degree

AU - Bonamy, Marthe

AU - Perrett, Thomas J.

PY - 2019

Y1 - 2019

N2 - Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most [Formula presented] paths. We confirm that conjecture for all graphs with maximum degree at most five.

AB - Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most [Formula presented] paths. We confirm that conjecture for all graphs with maximum degree at most five.

KW - 05C70

KW - Maximum degree

KW - Path decomposition

U2 - 10.1016/j.disc.2019.01.005

DO - 10.1016/j.disc.2019.01.005

M3 - Journal article

AN - SCOPUS:85060866629

SN - 0012-365X

VL - 342

SP - 1293

EP - 1299

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -

Gallai's path decomposition conjecture for graphs of small maximum degree

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this