Displaying similar documents to “Proof of an intersection theorem via graph homomorphisms.”

More on the complexity of cover graphs

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

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.

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.