|
|||||
|
|
Interval Minors of Complete Bipartite Graphs |
|
| Authors: | Bojan Mohar Arash Rafiey Behruz Tayfeh‐Rezaie Hehui Wu |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS, SIMON FRASER UNIVERSITY, BURNABY, BC, CANADASponsor: NSERC Discovery Grant (Canada);2. Sponsor: Canada Research Chair program;3. Contract grant number: Grant P1–0297 of ARRS (Slovenia).On leave from: IMFM, and FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.;4. INDIANA STATE UNIVERSITY IN;5. SIMON FRASER UNIVERSITY, BURNABY, BC, CANADA;6. SCHOOL OF MATHEMATICS, INSTITUTE FOR RESEARCH IN FUNDAMENTAL SCIENCES (IPM), TEHRAN, IRAN;7. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF MISSISSIPPI, OXFORD, MS |
| 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  ‐interval minor‐free bipartite graphs. We determine exact values when  and describe the extremal graphs. For  , lower and upper bounds are given and the structure of  ‐interval minor‐free graphs is studied. |
| Keywords: | complete bipartite graph forbidden configuration forbidden pattern interval minor Mathematics Subject Classification (2010): 05C35 05C83 05B20 |
