On Weak Flexibility in Planar Graphs

Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> such that any graph G in some graph class $$\mathscr {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> satisfies at least $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> proportion of the requests. More formally, for $$k &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> the goal is to prove that for any graph $$G \in \mathscr {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>C</mml:mi> </mml:mrow> </mml:math> on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> </mml:mrow> </mml:math> and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>:</mml:mo> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>R</mml:mi> <mml:mo>,</mml:mo> <mml:mspace/> <mml:mi>r</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>∈</mml:mo> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>|</mml:mo> <mml:mi>R</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:math> requests. If this is true, then $$\mathscr {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> is called $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>=</mml:mo> <mml:mi>V</mml:mi> </mml:mrow> </mml:math> . 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 there exists $$\varepsilon (b)&gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>(</mml:mo> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>4</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mn>5</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mn>6</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mn>7</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>b</mml:mi> </mml:msub> </mml:mrow> </mml:math> is weakly $$\varepsilon (b)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>(</mml:mo> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -flexible for lists of size 4 (here $$K_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> , $$C_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> and $$B_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ <mml:math xmlns:mml="h

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.