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

Marthe Bonamy*, Thomas J. Perrett

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

14 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 languageEnglish
JournalDiscrete Mathematics
Volume342
Issue number5
Pages (from-to)1293-1299
Number of pages7
ISSN0012-365X
DOIs
Publication statusPublished - 2019

Keywords

  • 05C70
  • Maximum degree
  • Path decomposition

Fingerprint Dive into the research topics of 'Gallai's path decomposition conjecture for graphs of small maximum degree'. Together they form a unique fingerprint.

Cite this