Flexibility of planar graphs—Sharpening the tools to get lists of size four
| Autor: | Michael Ferrara, Fuhong Ma, Ilkyoo Choi, Felix Christian Clemen, Tomáš Masařík, Paul Horn |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Vertex (graph theory) Class (set theory) Discrete Mathematics (cs.DM) 0102 computer and information sciences Sharpening Mathematical proof 01 natural sciences Combinatorics Set (abstract data type) symbols.namesake FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Fraction (mathematics) 0101 mathematics Mathematics Applied Mathematics 010102 general mathematics Graph theory Planar graph 05C15 010201 computation theory & mathematics symbols Combinatorics (math.CO) Computer Science - Discrete Mathematics |
| Zdroj: | Discrete Applied Mathematics |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2021.09.021 |
| Popis: | A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masa\v{r}\'ik and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\varepsilon$-flexible for list size $5$. Comment: 18 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect