Decomposition of Finite Graphs Into Forests

From MaRDI portal
Publication:5731396

DOI10.1112/jlms/s1-39.1.12zbMath0119.38805OpenAlexW2010042187WikidataQ56390697 ScholiaQ56390697MaRDI QIDQ5731396

C. St. J. A. Nash-Williams

Publication date: 1964

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/jlms/s1-39.1.12




Related Items (only showing first 100 items - show all)

The chromatic index of nearly bipartite multigraphsOn the first-order edge tenacity of a graphGroup connectivity of graphs with diameter at most 2Packing spanning trees in highly essentially connected graphsGood and semi-strong colorings of oriented planar graphsOn the toric ideals of matroids of a fixed rankThe monadic second order logic of graphs. VI: On several representations of graphs by relational structuresInduced and weak induced arboricitiesExtensions of matroid covering and packingTrees, paths, stars, caterpillars and spidersFacial packing edge-coloring of plane graphsFractional spanning tree packing, forest covering and eigenvaluesAdjacency queries in dynamic sparse graphsMinimum-maximal matching in series-parallel graphsGrünbaum colorings of triangulations on the projective planeOn the tree number of regular graphsOn constructive characterizations of \((k,l)\)-sparse graphsThe analysis of a nested dissection algorithmDecomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)Induced-path partition on graphs with special blocksEfficient computation of implicit representations of sparse graphsOn the thickness and arboricity of a graphThe reduction of graph families closed under contractionGraphs without spanning closed trailsImproved induced matchings in sparse graphsThe decompositions of line graphs, middle graphs and total graphs of complete graphs into forestsFlows and generalized coloring theorems in graphsOn globally sparse Ramsey graphsA property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphsA constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroidOn graph thickness, geometric thickness, and separator theoremsDecomposition of sparse graphs into two forests, one having bounded maximum degreeOn the game coloring index of \(F^+\)-decomposable graphsThree ways to cover a graphCyclic orderings and cyclic arboricity of matroidsSome inequalities for the Tutte polynomialSupereulerian graphs in the graph family \(C_{2}(6,k)\)Supereulerian graphs with width \(s\) and \(s\)-collapsible graphsConstructive characterizations for packing and covering with treesOn decomposing a hypergraph into \(k\) connected sub-hypergraphsCombined connectivity augmentation and orientation problemsBalanced generic circuits without long pathsSparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuitsFacial parity edge colouring of plane pseudographsLocal and union boxicityMinimum degree and minimum number of edge-disjoint trees3-uniform hypergraphs avoiding a given odd cycleDecomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graphColouring edges with many colours in cyclesDecomposition of bounded degree graphs into \(C_4\)-free subgraphsA linking polynomial of two matroidsOn the tractability of some natural packing, covering and partitioning problemsFacial packing vertex-coloring of subdivided plane graphsTwo packing problems on \(k\)-matroid treesGeneralized arboricity of graphs with large girthThe degree-diameter problem for sparse graph classesDecompositions of graphs into forests with bounded maximum degreeFacial edge ranking of plane graphs\(H(n)\)-factors in random graphsOn the planar split thickness of graphsClient-waiter games on complete and random graphsThickness and outerthickness for embedded graphsAn introduction to the discharging method via graph coloringThe coloring game on matroidsDecomposing a graph into forests and a matchingOn-line list coloring of matroidsAn enhancement of Nash-Williams' theorem on edge arboricity of graphsSubtree and substar intersection numbersOn the higher-order edge toughness of a graphImproved approximation algorithms for box contact representationsPin-collinear body-and-pin frameworks and the molecular conjectureStar arboricityA note on the arboricity of graphsDegree conditions for group connectivityThe generic rank of body-bar-and-hinge frameworksDuality in graph familiesFractional arboricity, strength, and principal partitions in graphs and matroidsDecomposition of sparse graphs, with application to game coloring numberBounded direction-length frameworksEdge-disjoint spanning trees and depth-first searchAn intermediate value theorem for the arboricitiesThe thickness and chromatic number of \(r\)-inflated graphsLocally finite graphs with ends: A topological approach. II: ApplicationsCovering planar graphs with forestsList total arboricity of 2-degenerate graphsOn maximally distant spanning trees of a graphThe tree number of a graph with a given girthA combinatorial study of the rigidity of planar structuresSublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decompositionOn partitions of graphs into treesCovering planar graphs with forests, one having bounded maximum degreeStructural theorems for submodular functions, polymatroids and polymatroid intersectionsOn star and caterpillar arboricityRooted \(k\)-connections in digraphsDecomposing a graph into forestsSparsity-certifying graph decompositionsThe game coloring number of planar graphsA short proof of Nash-Williams' theorem for the arboricity of a graphAcyclic edge-colorings of sparse graphs




This page was built for publication: Decomposition of Finite Graphs Into Forests