Bipartite graphs with no K6 minor
A theorem of Mader shows that every graph with average degree at least eight has a K6 minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2023
|
| _version_ | 1797111681495597056 |
|---|---|
| author | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_facet | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | A theorem of Mader shows that every graph with average degree at least eight has a K6 minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have K6 minors, but minimum degree six is certainly not enough. For every ε > 0 there are arbitrarily large graphs with average degree at least 8 − ε and minimum degree at least six, with no K6 minor.
<br>
But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every ε > 0 there are arbitrarily large bipartite graphs with average degree at least 8 − ε and no K6 minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a K6 |
| first_indexed | 2024-03-07T08:13:49Z |
| format | Journal article |
| id | oxford-uuid:3573a40d-9815-45d2-896c-47063bec740e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:13:49Z |
| publishDate | 2023 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:3573a40d-9815-45d2-896c-47063bec740e2023-12-14T12:12:47ZBipartite graphs with no K6 minorJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3573a40d-9815-45d2-896c-47063bec740eEnglishSymplectic ElementsElsevier2023Chudnovsky, MScott, ASeymour, PSpirkl, SA theorem of Mader shows that every graph with average degree at least eight has a K6 minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have K6 minors, but minimum degree six is certainly not enough. For every ε > 0 there are arbitrarily large graphs with average degree at least 8 − ε and minimum degree at least six, with no K6 minor. <br> But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every ε > 0 there are arbitrarily large bipartite graphs with average degree at least 8 − ε and no K6 minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a K6 |
| spellingShingle | Chudnovsky, M Scott, A Seymour, P Spirkl, S Bipartite graphs with no K6 minor |
| title | Bipartite graphs with no K6 minor |
| title_full | Bipartite graphs with no K6 minor |
| title_fullStr | Bipartite graphs with no K6 minor |
| title_full_unstemmed | Bipartite graphs with no K6 minor |
| title_short | Bipartite graphs with no K6 minor |
| title_sort | bipartite graphs with no k6 minor |
| work_keys_str_mv | AT chudnovskym bipartitegraphswithnok6minor AT scotta bipartitegraphswithnok6minor AT seymourp bipartitegraphswithnok6minor AT spirkls bipartitegraphswithnok6minor |