The linear arboricity of graphs

DOI10.1007/BF02783300zbMath0673.05019OpenAlexW2087518343WikidataQ56390824 ScholiaQ56390824MaRDI QIDQ1120581

Publication date: 1988

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02783300

zbMATH Keywords

path linear arboricity linear forest linear arboricity conjecture

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (60)

Complete subgraphs in a multipartite graph ⋮ A Planar linear arboricity conjecture ⋮ Bounded transversals in multipartite graphs ⋮ Jin Akiyama: a friend and his mathematics (on the occasion of his 60th birthday) ⋮ Acyclic coloring of graphs ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ Trees, paths, stars, caterpillars and spiders ⋮ An algorithmic approach to the Lovász local lemma. I ⋮ A parallel algorithmic version of the local lemma ⋮ Independent transversals in locally sparse graphs ⋮ The strong chromatic number of a graph ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ An average degree condition for independent transversals ⋮ Fair splittings by independent sets in sparse graphs ⋮ An efficient case for computing minimum linear arboricity with small maximum degree ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ The list linear arboricity of graphs ⋮ On the path partition number of 6‐regular graphs ⋮ Colorings, transversals, and local sparsity ⋮ Path decompositions of tournaments ⋮ Minimum number of disjoint linear forests covering a planar graph ⋮ Partitioning edges of a planar graph into linear forests and a matching ⋮ Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings ⋮ On graph thickness, geometric thickness, and separator theorems ⋮ Graphs of low average degree without independent transversals ⋮ Linear arboricity of degenerate graphs ⋮ A decomposition method on solving the linear arboricity conjecture ⋮ Partitioning into graphs with only small components ⋮ Almost Every Graph can be Covered by Linear Forests ⋮ On an \(f\)-coloring generalization of linear arboricity of multigraphs ⋮ Packing list‐colorings ⋮ Fair Representation by Independent Sets ⋮ Problems and results in extremal combinatorics. I. ⋮ Optimal path and cycle decompositions of dense quasirandom graphs ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Planar projections of graphs ⋮ Towards the linear arboricity conjecture ⋮ An introduction to the discharging method via graph coloring ⋮ A note on the arboricity of graphs ⋮ Reliable communication over highly connected noisy networks ⋮ Inapproximability of maximal strip recovery ⋮ Entropy compression versus Lovász local lemma ⋮ If (A+A)/(A+A) is small, then the ratio set is large ⋮ The conjunction of the linear arboricity conjecture and Lovász's path partition theorem ⋮ Unnamed Item ⋮ Finding occurrences of protein complexes in protein-protein interaction graphs ⋮ An asymptotic bound for the strong chromatic number ⋮ Eigenvalues of K1,k-Free Graphs and the Connectivity of Their Independence Complexes ⋮ The star arboricity of graphs ⋮ Finding independent transversals efficiently ⋮ Linear \(k\)-arboricity of Caylay graphs on abelian groups with given degree ⋮ Linear \(k\)-arboricities on trees ⋮ The linear arboricity of \(K_5\)-minor free graphs ⋮ Note on linear arboricity of graphs with large girth ⋮ Factorisation of regular graphs into forests of short paths ⋮ Incidence coloring of Cartesian product graphs ⋮ Upper bound for linear arboricity ⋮ Probabilistic methods in coloring and decomposition problems ⋮ Acyclic edge-colorings of sparse graphs

Cites Work

This page was built for publication: The linear arboricity of graphs