A survey and strengthening of Erdős-Gyarfas conjecture
type: Item
instance of: scholarly article
title: A survey and strengthening of Erdős-Gyarfas conjecture
zbMATH Open document ID: 1376.05043
author: Mushtaq A. Shah
author: Mridula Purohit
author: M. H. Gulzar
published in: Advances in Mathematics. Scientific Journal
publication date: 2017-11-20T00:00:00Z
review text: Erdős-Gyarfas conjecture states that every graph with minimum degree 3 contains a simple cycle whose length is a power of 2. In this paper, the authors prove that if a graph \(G\) of order \(n\) having \(n-2\) vertices of degree 3 and two vertices of degree 2 does not contain a cycle of length \(2^n\) and the distance between the vertices of degree 2 is \(n/2+1\) and this number is odd, then there exists a cubic graph which does not contain a cycle of length \(2^n\).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6810251
zbMATH Keywords: Erdős-Gyarfas conjecture
zbMATH Keywords: cycles of graph
zbMATH Keywords: cubic graph
zbMATH Keywords: connected graph
zbMATH Keywords: three connected graphs
MaRDI profile type: Publication
Recommended article: The Erdős-Hajnal conjecture. A survey
Recommended article: Q3982442
Recommended article: A strengthening of the Erdős-Szekeres theorem
Recommended article: A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
Recommended article: A note on the Erdős-Straus conjecture
Recommended article: A note on the Erd\H{o}-Straus Conjecture
Recommended article: On a Conjecture of Erdős, Gallai, and Tuza
Recommended article: On the Erdos-Straus conjecture
Recommended article: Q4347909
Recommended article: A generalization of the Erdős-Surányi problem
description: scientific article; zbMATH DE number 6810251