{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:13Z","timestamp":1740107113792,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1855653"],"award-info":[{"award-number":["DMS-1855653"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1953929"],"award-info":[{"award-number":["DMS-1953929"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,12]]},"abstract":"Abstract<\/jats:title>Recently, Dvo\u0159\u00e1k, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191\u2013206, 2019, https:\/\/doi.org\/10.1002\/jgt.22447<\/jats:ext-link>). In this new setting, each vertex v<\/jats:italic> in some subset of V<\/jats:italic>(G<\/jats:italic>) has a request for a certain color r<\/jats:italic>(v<\/jats:italic>) in its list of colors L<\/jats:italic>(v<\/jats:italic>). The goal is to find an L<\/jats:italic> coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\\varepsilon >0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that any graph G<\/jats:italic> in some graph class $$\\mathscr {C}$$<\/jats:tex-math>\n C<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfies at least $$\\varepsilon$$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> proportion of the requests. More formally, for $$k > 0$$<\/jats:tex-math>\n \n k<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the goal is to prove that for any graph $$G \\in \\mathscr {C}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n \u2208<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on vertex set V<\/jats:italic>, with any list assignment L<\/jats:italic> of size k<\/jats:italic> for each vertex, and for every $$R \\subseteq V$$<\/jats:tex-math>\n \n R<\/mml:mi>\n \u2286<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and a request vector $$(r(v): v\\in R, ~r(v) \\in L(v))$$<\/jats:tex-math>\n \n (<\/mml:mo>\n r<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n :<\/mml:mo>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n R<\/mml:mi>\n ,<\/mml:mo>\n \n r<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n \u2208<\/mml:mo>\n L<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, there exists an L<\/jats:italic>-coloring of G<\/jats:italic> satisfying at least $$\\varepsilon |R|$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n |<\/mml:mo>\n R<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> requests. If this is true, then $$\\mathscr {C}$$<\/jats:tex-math>\n C<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is called $$\\varepsilon$$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-flexible for lists of size <\/jats:italic>k<\/jats:italic>. Choi, Clemen, Ferrara, Horn, Ma, and Masa\u0159\u00edk (Discrete Appl Math 306:20\u2013132, 2022, https:\/\/doi.org\/10.1016\/j.dam.2021.09.021<\/jats:ext-link>) introduced the notion of weak flexibility<\/jats:italic>, where $$R = V$$<\/jats:tex-math>\n \n R<\/mml:mi>\n =<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b<\/jats:italic> there exists $$\\varepsilon (b)>0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n (<\/mml:mo>\n b<\/mml:mi>\n )<\/mml:mo>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 6<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 7<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n B<\/mml:mi>\n b<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is weakly $$\\varepsilon (b)$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n (<\/mml:mo>\n b<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-flexible for lists of size 4 (here $$K_n$$<\/jats:tex-math>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$C_n$$<\/jats:tex-math>\n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$B_n$$<\/jats:tex-math>\n \n B<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are the complete graph, a cycle, and a book on n<\/jats:italic> vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 6<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n C<\/mml:mi>\n 7<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n B<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is $$\\varepsilon$$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.<\/jats:p>","DOI":"10.1007\/s00373-022-02564-1","type":"journal-article","created":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T19:07:51Z","timestamp":1666897671000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Weak Flexibility in Planar Graphs"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8612-3594","authenticated-orcid":false,"given":"Bernard","family":"Lidick\u00fd","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[]},{"given":"Kyle","family":"Murphy","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5128-3771","authenticated-orcid":false,"given":"Shira","family":"Zerbib","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"key":"2564_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22849","author":"P Bradshaw","year":"2022","unstructured":"Bradshaw, P., Masa\u0159\u00edk, T., Stacho, L.: Flexible list colorings in graphs with special degeneracy conditions. J. Graph Theory (2022). https:\/\/doi.org\/10.1002\/jgt.22849","journal-title":"J. Graph Theory"},{"key":"2564_CR2","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.dam.2021.09.021","volume":"306","author":"I Choi","year":"2022","unstructured":"Choi, I., Clemen, F.C., Ferrara, M., Horn, P., Ma, F., Masa\u0159\u00edk, T.: Flexibility of planar graphs\u2014sharpening the tools to get lists of size four. Discrete Appl. Math. 306, 120\u2013132 (2022). https:\/\/doi.org\/10.1016\/j.dam.2021.09.021","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"2564_CR3","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1016\/j.disc.2016.11.022","volume":"340","author":"DW Cranston","year":"2017","unstructured":"Cranston, D.W., West, D.B.: An introduction to the discharging method via graph coloring. Discrete Math. 340(4), 766\u2013793 (2017). https:\/\/doi.org\/10.1016\/j.disc.2016.11.022","journal-title":"Discrete Math."},{"issue":"3","key":"2564_CR4","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1002\/jgt.22567","volume":"95","author":"Z Dvo\u0159\u00e1k","year":"2020","unstructured":"Dvo\u0159\u00e1k, Z., Masa\u0159\u00edk, T., Mus\u00edlek, J., Pangr\u00e1c, O.: Flexibility of planar graphs of girth at least six. J. Graph Theory 95(3), 457\u2013466 (2020). https:\/\/doi.org\/10.1002\/jgt.22567","journal-title":"J. Graph Theory"},{"issue":"4","key":"2564_CR5","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1002\/jgt.22634","volume":"96","author":"Z Dvo\u0159\u00e1k","year":"2021","unstructured":"Dvo\u0159\u00e1k, Z., Masa\u0159\u00edk, T., Mus\u00edlek, J., Pangr\u00e1c, O.: Flexibility of triangle-free planar graphs. J. Graph Theory 96(4), 619\u2013641 (2021). https:\/\/doi.org\/10.1002\/jgt.22634","journal-title":"J. Graph Theory"},{"issue":"3","key":"2564_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1002\/jgt.22447","volume":"92","author":"Z Dvo\u0159\u00e1k","year":"2019","unstructured":"Dvo\u0159\u00e1k, Z., Norin, S., Postle, L.: List coloring with requests. J. Graph Theory 92(3), 191\u2013206 (2019). https:\/\/doi.org\/10.1002\/jgt.22447","journal-title":"J. Graph Theory"},{"issue":"4","key":"2564_CR7","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1006\/eujc.2002.0570","volume":"23","author":"G Fijav\u017e","year":"2002","unstructured":"Fijav\u017e, G., Juvan, M., Mohar, B., \u0160krekovski, R.: Planar graphs without cycles of specific lengths. Eur. J. Combin. 23(4), 377\u2013388 (2002). https:\/\/doi.org\/10.1006\/eujc.2002.0570","journal-title":"Eur. J. Combin."},{"issue":"1","key":"2564_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jctb.1998.1893","volume":"76","author":"PCB Lam","year":"1999","unstructured":"Lam, P.C.B., Baogang, X., Liu, J.: The 4-choosability of plane graphs without 4-cycles. J. Combin. Theory Ser. B 76(1), 117\u2013126 (1999). https:\/\/doi.org\/10.1006\/jctb.1998.1893","journal-title":"J. Combin. Theory Ser. B"},{"key":"2564_CR9","doi-asserted-by":"publisher","unstructured":"Lidick\u00fd, B., Masa\u0159\u00edk, T., Murphy, K., Zerbib, S.: On weak flexibility in planar graphs. arXiv preprint (2020). https:\/\/doi.org\/10.48550\/ARXIV.2009.07932","DOI":"10.48550\/ARXIV.2009.07932"},{"key":"2564_CR10","unstructured":"Masa\u0159\u00edk, T.: Flexibility of planar graphs without 4-cycles. Acta Math. Univ. Comen. 88(3), 935\u2013940 (2019). http:\/\/www.iam.fmph.uniba.sk\/amuc\/ojs\/index.php\/amuc\/article\/view\/1182"},{"issue":"5","key":"2564_CR11","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1016\/s0893-9659(02)80007-6","volume":"15","author":"W Wang","year":"2002","unstructured":"Wang, W., Lih, K.-W.: Choosability and edge choosability of planar graphs without five cycles. Appl. Math. Lett. 15(5), 561\u2013565 (2002). https:\/\/doi.org\/10.1016\/s0893-9659(02)80007-6","journal-title":"Appl. Math. Lett."},{"key":"2564_CR12","doi-asserted-by":"publisher","unstructured":"Yang, D., Yang, F.: Flexibility of planar graphs without $$C_4$$ and $$C_5$$. arXiv preprint (2020). https:\/\/doi.org\/10.48550\/ARXIV.2006.05243","DOI":"10.48550\/ARXIV.2006.05243"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02564-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02564-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02564-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T19:28:33Z","timestamp":1670614113000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02564-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["2564"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02564-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"20 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"180"}}