Displaying similar documents to “Some recent results on duality and planarity”

Partitions of vertices

Jaroslav Nešetřil, Vojtěch Rödl (1976)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The list linear arboricity of planar graphs

Xinhui An, Baoyindureng Wu (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9. ...

Bipartite intersection graphs

Frank Harary, Jerald A. Kabell, Frederick R. McMorris (1982)

Commentationes Mathematicae Universitatis Carolinae

Similarity: