Covering a graph with cuts of minimum total size

DOI10.1016/S0012-365X(00)00367-8zbMath0982.05059OpenAlexW1988483130MaRDI QIDQ5939921

André Kündgen, Zoltan Fueredi

Publication date: 23 July 2001

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00367-8

zbMATH Keywords

planar graphschromatic numberrandom graphbandwidth-sumcut-covergeometric representationgraph coveringNordhaus-Gaddum typeTurán graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

An overview of graph covering and partitioning ⋮ On the biclique cover of the complete graph ⋮ Covering complete hypergraphs with cuts of minimum total size ⋮ On biclique coverings ⋮ A bound on the total size of a cut cover ⋮ Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs

This page was built for publication: Covering a graph with cuts of minimum total size