Linear arboricity and linear k-arboricity of regular graphs

Noga Alon, V. J. Teague, N. C. Wormald

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs.

Original languageEnglish (US)
Pages (from-to)11-16
Number of pages6
JournalGraphs and Combinatorics
Volume17
Issue number1
DOIs
StatePublished - Jan 1 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Linear arboricity and linear k-arboricity of regular graphs'. Together they form a unique fingerprint.

  • Cite this