Interval minors of complete bipartite graphs

2014/08/06 by Bojan Mohar, Arash Rafiey, Mohar, Bojan +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1408.1155

arxiv created 2014/08/06 · arxiv updated 2014/08/07

Abstract

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley-Wilf limits. We investigate the maximum number of edges in K_r,s-interval minor free bipartite graphs. We determine exact values when r=2 and describe the extremal graphs. For r=3, lower and upper bounds are given and the structure of K_3,s-interval minor free graphs is studied.

Cited by

• A Polynomial-Time Approximation Algorithm for Complete Interval Minors

Related

• Interval minors of complete multipartite graphs
• On the number of graphs not containing K_3,3 as a minor
• The extremal function for K₉^= minors
• Extremal K₄-minor-free graphs without short cycles
• Minors in expanding graphs