Covering Multigraphs by Simple Circuits

DOI10.1137/0606035MaRDI QIDQ3703929zbMATH OpenOpenAlexFDO

Authors Noga Alon, Michael Tarsi

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606035

zbMATH Keywords

bridgeless multigraphEulerian subgraphsgraph algorithmsminimum covernowhere-zero flow

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Covering Graphs by Cycles
• Minimum cycle coverings and integer flows
• Cycle covering in bridgeless graphs
• Shortest circuit covers of cubic graphs
• Cycle covers of graphs with a nowhere-zero 4-flow

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Covering Graphs by Simple Circuits
• Flows and generalized coloring theorems in graphs
• Integer flows
• Nowhere-zero 6-flows
• On the eulericity of a graph
• Shortest coverings of graphs with cycles

Cited in

(50)

• Nowhere zero flow and circuit covering in regular matroids
• Integer flows and cycle covers
• Short cycle covers and the cycle double cover conjecture
• A parallel algorithm for approximating the minimum cycle cover
• Extensions of flow theorems
• Covering a graph with cycles.
• Covers of Eulerian graphs
• Proofs of two minimum circuit cover conjectures
• Shortest circuit covers of signed graphs
• Short signed circuit covers of signed graphs
• Integer 4-flows and cycle covers
• Circuit decompositions and shortest circuit coverings of hypergraphs
• Circuit coverings of graphs and a conjecture of Pyber
• Towards obtaining a 3-decomposition from a perfect matching
• An overview of graph covering and partitioning
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• Short cycle covers of graphs with at most 77\% vertices of degree two
• Signed circuit cover of bridgeless signed graphs
• A bound on the total size of a cut cover
• A note about shortest cycle covers
• A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface
• Circuit \(k\)-covers of signed graphs
• Short cycle covers on cubic graphs by choosing a 2-factor
• A note on shortest cycle covers of cubic graphs
• Short cycle covers of graphs and nowhere-zero flows
• Characteristic flows on signed graphs and short circuit covers
• Circuit covers of signed graphs
• On a property of cyclic covers ofp-graphs
• Covering Graphs by Cycles
• scientific article; zbMATH DE number 475603 (Why is no real title available?)
• Short cycle covers of cubic graphs
• Smallest (1, 2)‐eulerian weight and shortest cycle covering
• Graphs with the Circuit Cover Property
• Multimatroids I. Coverings by Independent Sets
• Generation and properties of snarks
• 1-factor and cycle covers of cubic graphs
• Minimum \(T\)-joins and signed-circuit covering
• Cubic graphs with no short cycle covers
• Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits
• Circuit covers of signed Eulerian graphs
• Some snarks are worse than others
• Five-cycle double cover and shortest cycle cover
• On Fan's conjecture about 4-flow
• Signed cycle double covers
• Signed circuit 6-covers of signed K₄-minor-free graphs
• 4-coverable snarks, perfect matching cover, and Isaacs product
• An infinite family of snarks with perfect matching cover index 4
• A note on Alon-Tarsi shortest cycle cover conjecture
• Covering weighted graphs by even subgraphs
• Shipper collaboration

This page was built for publication: Covering Multigraphs by Simple Circuits

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