Displaying similar documents to “Recurrence and transience of the edge graph of a tiling of the euclidean 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 transitive orientations of G-ê

Michael Andresen (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

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...

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.