Displaying similar documents to “Partitioning a planar graph without chordal 5-cycles into two forests”

On long cycles through four prescribed vertices of a polyhedral graph

Jochen Harant, Stanislav Jendrol', Hansjoachim Walther (2008)

Discussiones Mathematicae Graph Theory

Similarity:

For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.

A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs

Wojciech Wide (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2. For a given graph H we say that G is H-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies that at least one of them is super-heavy. For a family of graphs H we say that G is H-f1-heavy, if G is H-f1-heavy for...

On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph

David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein (2010)

Discussiones Mathematicae Graph Theory

Similarity:

We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.

L(2, 1)-Labelings of Some Families of Oriented Planar Graphs

Sagnik Sen (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.