Displaying similar documents to “On the Erdős-Gyárfás Conjecture in Claw-Free Graphs”

Cycles through specified vertices in triangle-free graphs

Daniel Paulusma, Kiyoshi Yoshimoto (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ₄ are best possible.

Forbidden Pairs and (k,m)-Pancyclicity

Charles Brian Crane (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs...

A Survey of the Path Partition Conjecture

Marietjie Frick (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

A Note on Barnette’s Conjecture

Jochen Harant (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.