Towards the Erdős-Gallai cycle decomposition conjecture

DOI10.1145/3564246.3585218MaRDI QIDQ6499269zbMATH OpenFDO

Authors Matija Bucić, Richard Montgomery

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585218

zbMATH Keywords

decomposition into expandersErdős-Galla conjecturegraph decompositionrobust sublinear expanders

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A generalization of permanent inequalities and applications in counting and optimization
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• A solution to Erdős and Hajnal’s odd cycle problem
• An Erdős-Gallai conjecture
• Clique immersion in graphs without a fixed bipartite graph
• Covering the edges of a connected graph by paths
• Covers of Eulerian graphs
• Crux and Long Cycles in Graphs
• Cycle packing
• Decomposing random graphs into few cycles and edges
• Expander graphs and their applications
• Extremal density for sparse minors and subdivisions
• Gallai's conjecture for disconnected graphs
• Hall's theorem for hypergraphs
• How to build a pillar: a proof of Thomassen's conjecture
• scientific article; zbMATH DE number 426361 (Why is no real title available?)
• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• scientific article; zbMATH DE number 3143608 (Why is no real title available?)
• scientific article; zbMATH DE number 3857112 (Why is no real title available?)
• scientific article; zbMATH DE number 4214053 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1775414 (Why is no real title available?)
• scientific article; zbMATH DE number 871922 (Why is no real title available?)
• scientific article; zbMATH DE number 3253072 (Why is no real title available?)
• scientific article; zbMATH DE number 3349865 (Why is no real title available?)
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Logarithmically small minors and topological minors
• Long cycles in locally expanding graphs, with applications
• Long cycles in subgraphs of (pseudo)random directed graphs
• Nested cycles with no geometric crossings
• On Graph Complexity
• On the combinatorial problems which I would most like to see solved
• On the coverings of graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Path and cycle decompositions of dense graphs
• Rainbow Turán number of clique subdivisions
• Ramsey numbers of cycles versus general graphs
• Small complete minors above the extremal edge density
• Subexponential algorithms for unique games and related problems
• Subgraph coverings and edge switchings
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• The Extremal Number of Tight Cycles
• The probabilistic method
• The Representation of a Graph by Set Intersections
• Topological Cliques in Graphs
• Topological cliques in graphs II
• Tree embeddings
• Unique games on expanding constraint graphs are easy (extended abstract)
• Well-mixing vertices and almost expanders
• What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?

Cited in

(3)

• Separating the edges of a graph by cycles and by subdivisions of K₄
• Regular bipartite decompositions of pseudorandom graphs
• Path odd-covers of graphs

This page was built for publication: Towards the Erdős-Gallai cycle decomposition conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499269)