Almost Every Graph can be Covered by Linear Forests

DOI10.1017/S0963548300001632MaRDI QIDQ4862746zbMATH OpenFDO

Authors Colin McDiarmid, Bruce Reed

Publication date 12 February 1996

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

maximum degreerandom variableprobabilistic methodslinear arboricitylinear forest

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The linear arboricity of graphs
• scientific article; zbMATH DE number 566421
• The list linear arboricity of graphs
• Towards the linear arboricity conjecture
• The conjunction of the linear arboricity conjecture and Lovász's path partition theorem

Cites work

• COVERING AND PACKING IN GRAPHS, I.
• Canonical edge-colourings of locally finite graphs
• Covering and packing in graphs IV: Linear arboricity
• Linear arboricity of random regular graphs
• Probabilistic methods in coloring and decomposition problems
• Probability Inequalities for Sums of Bounded Random Variables
• Some results on linear arboricity
• The linear arboricity of graphs
• The linear arboricity of some regular graphs
• The tail of the hypergeometric distribution

Cited in

(4)

• Note on linear arboricity of graphs with large girth
• On the linearK-arboricity of cubic graphs
• Towards the linear arboricity conjecture
• Graph factors and factorization: 1985--2003: a survey

This page was built for publication: Almost Every Graph can be Covered by Linear Forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862746)