Displaying similar documents to “Embedding of graphs in the projective plane”

1-factors and characterization of reducible faces of plane elementary bipartite graphs

Andrej Taranenko, Aleksander Vesel (2012)

Discussiones Mathematicae Graph Theory

Similarity:

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection...

On the strong parity chromatic number

Július Czap, Stanislav Jendroľ, František Kardoš (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.

An Extension of Kotzig’s Theorem

Valerii A. Aksenov, Oleg V. Borodin, Anna O. Ivanova (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2...