Flexible list coloring of graphs with maximum average degree less than $3$
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912205920796672 |
|---|---|
| author | Bi, Richard Bradshaw, Peter |
| author_facet | Bi, Richard Bradshaw, Peter |
| contents | In the flexible list coloring problem, we consider a graph $G$ and a color list assignment $L$ on $G$, as well as a subset $U \subseteq V(G)$ for which each $u \in U$ has a preferred color $p(u) \in L(u)$. Our goal is to find a proper $L$-coloring $ϕ$ of $G$ such that $ϕ(u) = p(u)$ for at least $ε|U|$ vertices $u \in U$. We say that $G$ is $ε$-flexibly $k$-choosable if for every $k$-size list assignment $L$ on $G$ and every subset of vertices with coloring preferences, $G$ has a proper $L$-coloring that satisfies an $ε$ proportion of these coloring preferences. Dvořák, Norin, and Postle [Journal of Graph Theory, 2019] asked whether every $d$-degenerate graph is $ε$-flexibly $(d+1)$-choosable for some constant $ε= ε(d) > 0$.
In this paper, we prove that there exists a constant $ε> 0$ such that every graph with maximum average degree less than $3$ is $ε$-flexibly $3$-choosable, which gives a large class of $2$-degenerate graphs which are $ε$-flexibly $(d+1)$-choosable. In particular, our results imply a theorem of Dvořák, Masařík, Musílek, and Pangrác [Journal of Graph Theory, 2020] stating that every planar graph of girth $6$ is $ε$-flexibly $3$-choosable for some constant $ε> 0$. To prove our result, we generalize the existing reducible subgraph framework traditionally used for flexible list coloring to allow reducible subgraphs of arbitrarily large order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02979 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Flexible list coloring of graphs with maximum average degree less than $3$ Bi, Richard Bradshaw, Peter Combinatorics 05C15 In the flexible list coloring problem, we consider a graph $G$ and a color list assignment $L$ on $G$, as well as a subset $U \subseteq V(G)$ for which each $u \in U$ has a preferred color $p(u) \in L(u)$. Our goal is to find a proper $L$-coloring $ϕ$ of $G$ such that $ϕ(u) = p(u)$ for at least $ε|U|$ vertices $u \in U$. We say that $G$ is $ε$-flexibly $k$-choosable if for every $k$-size list assignment $L$ on $G$ and every subset of vertices with coloring preferences, $G$ has a proper $L$-coloring that satisfies an $ε$ proportion of these coloring preferences. Dvořák, Norin, and Postle [Journal of Graph Theory, 2019] asked whether every $d$-degenerate graph is $ε$-flexibly $(d+1)$-choosable for some constant $ε= ε(d) > 0$. In this paper, we prove that there exists a constant $ε> 0$ such that every graph with maximum average degree less than $3$ is $ε$-flexibly $3$-choosable, which gives a large class of $2$-degenerate graphs which are $ε$-flexibly $(d+1)$-choosable. In particular, our results imply a theorem of Dvořák, Masařík, Musílek, and Pangrác [Journal of Graph Theory, 2020] stating that every planar graph of girth $6$ is $ε$-flexibly $3$-choosable for some constant $ε> 0$. To prove our result, we generalize the existing reducible subgraph framework traditionally used for flexible list coloring to allow reducible subgraphs of arbitrarily large order. |
| title | Flexible list coloring of graphs with maximum average degree less than $3$ |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2310.02979 |