Loading...
Please wait, while we are loading the content...
Similar Documents
Separation Choosability and Dense Bipartite Induced Subgraphs
| Content Provider | Scilit |
|---|---|
| Author | Esperet, Louis Kang, Ross J. Thomassé, Stéphan |
| Copyright Year | 2019 |
| Description | We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree d contain a bipartite induced subgraph of minimum degree Ω(log d) as d→∞? |
| Related Links | http://arxiv.org/pdf/1802.03727 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/265127482211C42CA56294C8468D0FEF/S0963548319000026a.pdf/div-class-title-separation-choosability-and-dense-bipartite-induced-subgraphs-div.pdf |
| Ending Page | 732 |
| Page Count | 13 |
| Starting Page | 720 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548319000026 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 5 |
| Volume Number | 28 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2019-02-26 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05c15 Secondary 05c35 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
