The height of a 4-cycle in triangle-free 1-planar graphs with minimum degree 5

Oleg Veniaminovich Borodin, I. G. Dmitriev, Anna O. Ivanova · Journal of Applied and Industrial Mathematics · 2009

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. It is known that each 1-planar graph has a vertex of degree at most 7, and also either a vertex of degree at most 4 or a cycle of length at most 4. In the article, it is proven that each triangle-free 1-planar graph of degree less than 5 has a 4-cycle that consists of vertices of degree at most 8.

Read the paper · More papers on PaperTik