Almost Every Graph can be Covered by Linear Forests

DOI10.1017/S0963548300001632zbMATH Open0852.05069MaRDI QIDQ4862746FDOQ4862746

Authors: Colin McDiarmid, Bruce Reed 

Publication date: 12 February 1996

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

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

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)

Cites Work

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

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)