Any four independent edges of a 4-connected graph are contained in a circuit
type: Item
instance of: scholarly article
title: Any four independent edges of a 4-connected graph are contained in a circuit
zbMATH Open document ID: 0588.05024
DOI: 10.1007/BF01955745
published in: Acta Mathematica Hungarica
publication date: 1985-01-01T00:00:00Z
review text: L. Lovász raised the following conjecture: Suppose L is a set of k independent edges in a k-connected graph G (k\(\geq 2)\), and if k is odd then G-L is connected. Then G has a circuit containing all edges of L. This conjecture is proved for \(k=3\) by \textit{L. Lovász} [Combinatorial problems and exercises, North-Holland (1978; Zbl 0439.05001), {\S}6.67]. \textit{R. Häggkvist} and \textit{C. Thomassen} proved the same conclusion follows if G is \((k+1)\)-connected [Discrete Math. 41, 29-34 (1982; Zbl 0488.05048)]. In this paper, the authors prove the conjecture holds for \(k=4\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3943847
zbMATH Keywords: independent edges
zbMATH Keywords: connected graph
zbMATH Keywords: circuit
author: Péter L. Erdős
author: Ervin Győri
MaRDI profile type: Publication
cites work: Circuits through specified edges
cites work: Q3880849
cites work: An Erdős-Gallai conjecture
full work available at URL: https://doi.org/10.1007/bf01955745
OpenAlex ID: W2077560266
description: scientific article; zbMATH DE number 3943847