Generalized arboricity of graphs with large girth

DOI10.1016/j.disc.2019.01.018zbMath1407.05085OpenAlexW2911399964MaRDI QIDQ1732768

Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Michał Farnik, Zofia Miechowicz, Tomasz Bartnicki

Publication date: 25 March 2019

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

Full work available at URL: https://doi.org/10.1016/j.disc.2019.01.018

zbMATH Keywords

arboricityentropy compressionacyclic chromatic indexbounded expansion

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items

Edge-coloring of plane multigraphs with many colors on facial cycles, Moser-Tardos resampling algorithm, entropy compression method and the subset gas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring edges with many colours in cycles
• Nonrepetitive colouring via entropy compression
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposing a graph into forests
• Generalised acyclic edge colourings of graphs with large girth
• On the perfect one-factorization conjecture
• Acyclic edge-coloring using entropy compression
• Bounds on the generalised acyclic chromatic numbers of bounded degree graphs
• Acyclic edge colorings of graphs
• Structural sparsity
• An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• A constructive proof of the general lovász local lemma
• Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution
• New approach to nonrepetitive sequences
• Decomposition of Finite Graphs Into Forests