A Planar linear arboricity conjecture

DOI10.1002/jgt.20592zbMath1242.05064arXiv0912.5528OpenAlexW2949301751WikidataQ122981990 ScholiaQ122981990MaRDI QIDQ2891050

Marek Cygan, Łukasz Kowalik, Borut Lužar, Jian Liang Wu, Jian-Feng Hou

Publication date: 13 June 2012

Published in: Lecture Notes in Computer Science, Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.5528

zbMATH Keywords

linear forestssimple graph of maximum degree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Trees, paths, stars, caterpillars and spiders, Trees, Paths, Stars, Caterpillars and Spiders, An efficient case for computing minimum linear arboricity with small maximum degree, Edge coloring of signed graphs, The structure of plane graphs with independent crossings and its applications to coloring problems, Minimum number of disjoint linear forests covering a planar graph, Partitioning edges of a planar graph into linear forests and a matching, Linear arboricity of degenerate graphs, A decomposition method on solving the linear arboricity conjecture, Vizing's adjacency lemma on edge chromatic critical signed graphs and its applications, Edge covering pseudo-outerplanar graphs with forests, Unnamed Item, The linear arboricity of planar graphs with maximum degree at least 5, Unnamed Item, On the linear arboricity of graphs embeddable in surfaces, An introduction to the discharging method via graph coloring, Linear arboricity of outer-1-planar graphs, The list linear arboricity of planar graphs with 7-cycles containing at most two chords, Linear arboricity of NIC-planar graphs, Linear \(k\)-arboricity of Caylay graphs on abelian groups with given degree, The linear arboricity of \(K_5\)-minor free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The linear arboricity of planar graphs with no short cycles
• The linear arboricity of graphs
• A data structure for dynamic trees
• New linear-time algorithms for edge-coloring planar graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• The linear arboricity of planar graphs of maximum degree seven is four
• The linear arboricity of some regular graphs
• Covering and packing in graphs IV: Linear arboricity
• Complexité de l'arboricité linéaire d'un graphe
• A Generalization of Kotzig’s Theorem and Its Application
• COVERING AND PACKING IN GRAPHS, I.
• Linear arboricity and linear \(k\)-arboricity of regular graphs