Linear arboricity and linear k-arboricity of regular graphs

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

doi:10.1007/PL00007233

Linear arboricity and linear k-arboricity of regular graphs

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

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

35 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 language	English (US)
Pages (from-to)	11-16
Number of pages	6
Journal	Graphs and Combinatorics
Volume	17
Issue number	1
DOIs	https://doi.org/10.1007/PL00007233
State	Published - 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/PL00007233

Cite this

@article{1432c357e36d4c6ea7add94b5f520079,

title = "Linear arboricity and linear k-arboricity of regular graphs",

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.",

author = "Noga Alon and Teague, {V. J.} and Wormald, {N. C.}",

year = "2001",

doi = "10.1007/PL00007233",

language = "English (US)",

volume = "17",

pages = "11--16",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Linear arboricity and linear k-arboricity of regular graphs

AU - Alon, Noga

AU - Teague, V. J.

AU - Wormald, N. C.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0013536034&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013536034&partnerID=8YFLogxK

U2 - 10.1007/PL00007233

DO - 10.1007/PL00007233

M3 - Article

AN - SCOPUS:0013536034

SN - 0911-0119

VL - 17

SP - 11

EP - 16

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Linear arboricity and linear k-arboricity of regular graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this