Minmax degree of graphs (Extended abstract)

The minmax degree of a graph G, denoted M⁎(G), is the largest integer m such that every edge of G is incident with a vertex with degree at least m. The tight bounds are known for the minmax degree of planar graphs with minimum degree at least 2 and girth g for every g, unless when g=3 or g=4. For these last values of g, we can find for any integer k a graph with M⁎(G)⩾k.We define the 2-stackability of a graph G, denoted maxS2(G), as the maximum number of vertices with degree 2 that all are adjacent to the same pair of distinct vertices in G. In the complete version of the paper, we prove that, for a planar graph G with minimum degree at least 2, M⁎(G)⩽5(maxS2(G)+2); moreover, M⁎(G)⩽5(maxS2(G)+1) if G does not contain triangles. We also show that these bounds are tight.The maximum average degree of a graph G is mad(G)=max{2|E(G)||V(G)|;H⊆G}. We prove that, for every δ⩾2 and k⩾δ, every graph G with δ(G)⩾δ and mad(G)<2δ(k+1)δ+k+1 has M⁎(G)⩽k. We also show that these bound is the lowest possible.Borodin et al. [Borodin, O. V., A. V. Kostochka, N. N. Sheikh and G. Yu, M-degrees of quadrangle-free planar graph, J. Graph Theory 60 (2009), pp. 80-85] showed that M⁎(G)⩽7 if G is a planar graph with minimum degree at least 2 and without 4-cycles. Moreover, if G has neither 5-cycles, Borodin et al. [5] proved that M⁎(G)⩽5. We prove that a planar graph G has M⁎(G)⩽5 if G has minimum degree at least 2, no 4-cycles, neither 5-cycles adjacent to a triangle incident to a vertex of degree 2. We give some other results about planar graphs with minimum degree at least 2 and without 4-cycles and intersecting triangles, with other restrictions on the cycles. These results imply results for edge-partitions of graphs and game coloring number.