Interval Minors of Complete Bipartite Graphs. Issue 3 (24th August 2015)

• Record Type: Journal Article
• Authors: Mohar, Bojan; Rafiey, Arash; Tayfeh‐Rezaie, Behruz; Wu, Hehui
• Is Part Of: Journal of graph theory. Volume 82:Issue 3(2016)
• Page Start: 312
• Page End: 321
• Publication Date: 2015-08-24
• Subjects: complete bipartite graph -- forbidden configuration -- forbidden pattern -- interval minor Mathematics Subject Classification (2010): 05C35 -- 05C83 -- 05B20; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21903
• Languages: English
• ISSNs: 0364-9024

Abstract

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.