The star arboricity of graphs

DOI10.1016/0012-365X(89)90073-3zbMath0684.05033OpenAlexW2128081519MaRDI QIDQ1825208

Noga Alon, I. Algor

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(89)90073-3

zbMATH Keywords

algorithmprobability spacestar arboricityd-regular graph

Mathematics Subject Classification ID

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

Related Items

Induced and weak induced arboricities, Facial incidence colorings of embedded multigraphs, Incidence coloring on hypercubes, On incidence coloring conjecture in Cartesian products of graphs, Distinguishing arc-colourings of symmetric digraphs, An algorithmic approach to the Lovász local lemma. I, A parallel algorithmic version of the local lemma, On incidence coloring and star arboricity of graphs, The acircuitic directed star arboricity of subcubic graphs is at most four, Star arboricity of graphs, The linear arboricity of graphs, Note on incidence chromatic number of subquartic graphs, Bounds on directed star arboricity in some digraph classes, A novel approach for cyclic decompositions of balanced complete bipartite graphs into infinite graph classes, On globally sparse Ramsey graphs, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Simultaneous coloring of vertices and incidences of outerplanar graphs, On incidence coloring of complete multipartite and semicubic bipartite graphs, Three ways to cover a graph, On spanning galaxies in digraphs, Defective incidence coloring of graphs, Monochromatic subgraphs in iterated triangulations, Indicated coloring of matroids, Independent sets in regular graphs and sum-free subsets of finite groups, WDM and Directed Star Arboricity, NP-completeness of 4-incidence colorability of semi-cubic graphs, The game of arboricity, On incidence choosability of cubic graphs, Star arboricity, Interval incidence graph coloring, The incidence coloring conjecture for graphs of maximum degree 3, Incidence coloring of pseudo-Halin graphs, The incidence coloring numbers of meshes, Star number and star arboricity of a complete multigraph, Acyclic colouring of 1-planar graphs, On the decomposition of graphs into complete bipartite graphs, Incidence coloring of the squares of some graphs, Separation dimension and degree, Incidence coloring of mycielskians with fast algorithm, Incidence coloring of \(k\)-degenerated graphs, A Note on Incidence graphs, Planar Ramsey graphs, Some results on the incidence coloring number of a graph, Acyclic \(k\)-strong coloring of maps on surfaces, Spanning galaxies in digraphs, 2-star-coloring of graphs, On some arboricities in planar graphs, Incidence coloring of Cartesian product graphs, Probabilistic methods in coloring and decomposition problems, Incidence coloring of graphs with high maximum average degree, Some colouring problems for Paley graphs

Cites Work

• The linear arboricity of graphs
• Graphs which contain all small graphs
• The star-arboricity of the complete regular multipartite graphs
• The linear arboricity of some regular graphs
• Covering and packing in graphs IV: Linear arboricity
• A Constructive Solution to a Tournament Problem
• Decomposition of Finite Graphs Into Forests
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item