Displaying similar documents to “A structural property of planar graphs and the simultaneous colouring of their edges and faces”

Light edges in 1-planar graphs with prescribed minimum degree

Dávid Hudák, Peter Šugerek (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains...