An Erdős-Gallai conjecture
type: Item
instance of: scholarly article
title: An Erdős-Gallai conjecture
zbMATH Open document ID: 0581.05043
DOI: 10.1007/BF02579444
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: The following conjecture (1966) of P. Erdős and T. Gallai is confirmed: Every graph on n vertices can be covered by n-1 circuits and edges. A slightly stronger form of the planar case of this conjecture was formerly proved by Tao Mao-qi, Shen Yun-qiu and Ku Tung-shin (preprint), stating that every 2-edge-connected planar graph can be covered by n-2 circuits. The present paper gives a shorter proof. In addition, two other related results are also established.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3929051
zbMATH Keywords: paths
zbMATH Keywords: circuit covering
author: Laszló Pyber
Wikidata QID: Q122889057
MaRDI profile type: Publication
cites work: The Representation of a Graph by Set Intersections
cites work: Q5670636
cites work: Q4111952
Recommended article: A Conjecture of Erdos
Recommended article: On a conjecture of Erdős
Recommended article: ON A CONJECTURE OF ERDÖS
Recommended article: Erdős and Rényi conjecture
Recommended article: On a Conjecture of Erdős, Gallai, and Tuza
Recommended article: Q4552186
Recommended article: On the Erdos-Straus conjecture
description: scientific article; zbMATH DE number 3929051