{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:19:53Z","timestamp":1759335593946},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T00:00:00Z","timestamp":1551139200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>d<\/jats:italic> contain a bipartite induced subgraph of minimum degree \u03a9(log <jats:italic>d<\/jats:italic>) as <jats:italic>d<\/jats:italic>\u2192\u221e?<\/jats:p>","DOI":"10.1017\/s0963548319000026","type":"journal-article","created":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T23:29:58Z","timestamp":1551137398000},"page":"720-732","source":"Crossref","is-referenced-by-count":11,"title":["Separation Choosability and Dense Bipartite Induced Subgraphs"],"prefix":"10.1017","volume":"28","author":[{"given":"Louis","family":"Esperet","sequence":"first","affiliation":[]},{"given":"Ross J.","family":"Kang","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,2,26]]},"reference":[{"key":"S0963548319000026_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548319000026_ref20","unstructured":"[20] Johansson, A. (1996) Asymptotic choice number for triangle-free graphs. Technical Report 91-5, DIMACS."},{"key":"S0963548319000026_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200007)16:4<364::AID-RSA5>3.0.CO;2-0"},{"key":"S0963548319000026_ref9","unstructured":"[9] Brandt, S. and Thomass\u00e9, S. (2011) Dense triangle-free graphs are four-colorable: A solution to the Erd\u0151s\u2013Simonovits problem. Manuscript."},{"key":"S0963548319000026_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.06.016"},{"key":"S0963548319000026_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20040"},{"key":"S0963548319000026_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10045"},{"key":"S0963548319000026_ref10","unstructured":"[10] Cames van Batenburg, W. , de Joannis de Verclos, R. , Kang, R. J. and Pirot, F. (2018) Bipartite induced density in triangle-free graphs. arXiv:1808.02512"},{"key":"S0963548319000026_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-010-0247-x"},{"key":"S0963548319000026_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070305"},{"key":"S0963548319000026_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"S0963548319000026_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01608526"},{"key":"S0963548319000026_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1361-2"},{"key":"S0963548319000026_ref14","first-page":"125","volume-title":"Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing","author":"Erd\u0151s","year":"1980"},{"key":"S0963548319000026_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21754"},{"key":"S0963548319000026_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051124"},{"key":"S0963548319000026_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.06.007"},{"key":"S0963548319000026_ref17","unstructured":"[17] Harris, D. G. (2016) Some results on chromatic number as a function of triangle count. arXiv:1604.00438"},{"key":"S0963548319000026_ref18","unstructured":"[18] Havet, F. (2017) Finding more than an even hole. Manuscript."},{"key":"S0963548319000026_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/070698385"},{"key":"S0963548319000026_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548319000026_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199801)27:1<43::AID-JGT7>3.0.CO;2-G"},{"key":"S0963548319000026_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00101-0"},{"key":"S0963548319000026_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"S0963548319000026_ref27","first-page":"175","volume-title":"Random Graphs \u201887","author":"Matula","year":"1990"},{"key":"S0963548319000026_ref30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21651"},{"key":"S0963548319000026_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548319000026_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548319000026_ref33","first-page":"10","article-title":"Coloring the vertices of a graph in prescribed colors","volume":"29","author":"Vizing","year":"1976","journal-title":"Diskret. Analiz"},{"key":"S0963548319000026_ref25","unstructured":"[25] Kwan, M. , Letzter, S. , Sudakov, B. and Tran, T. (2018) Dense induced bipartite subgraphs in triangle-free graphs. arXiv:1810.12144"},{"key":"S0963548319000026_ref21","unstructured":"[21] Johansson, A. (1996) The choice number of sparse graphs. Manuscript."},{"key":"S0963548319000026_ref13","unstructured":"[13] Davies, E. , de Joannis de Verclos, R. , Kang, R. J. and Pirot, F. (2018) Colouring triangle-free graphs with local list sizes. arXiv:1812.11152"},{"key":"S0963548319000026_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80014-5"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T03:51:25Z","timestamp":1568173885000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000026\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,26]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548319000026"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000026","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,26]]}}}