Flexible DP-4-coloring of planar graphs without 4-cycles and intersecting triangles
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917524629618688 |
|---|---|
| author | Fang, Shu Liu, Runrun Yu, Gexin |
| author_facet | Fang, Shu Liu, Runrun Yu, Gexin |
| contents | Graph coloring with preferences offers a powerful framework for constraint satisfaction problems in which fulfilling every request is impossible but satisfying a guaranteed positive fraction is highly desirable. A \emph{request} on a graph $G$ equipped with a list assignment $L$ assigns to each vertex of some subset $dom(r)\subseteq V(G)$ a preferred color from its list. Following Dvořák, Norin, and Postle (2019), $G$ is \emph{$\varepsilon$-flexibly $k$-choosable} if, for every $k$-list assignment $L$ and every request $r$, there is an $L$-coloring of $G$ that agrees with $r$ on at least $\varepsilon|dom(r)|$ vertices. The corresponding notion for DP-coloring (correspondence coloring) was formalized by Bradshaw, Choi, and Kostochka (2025). Choi, Clemen, Ferrara, Horn, Ma, and Masařík (2022) proved that every planar graph without $4$-cycles and with $3$-cycle distance at least $2$ is $\varepsilon$-flexibly $4$-choosable. We improve the result in two respects: weakening the hypothesis from $3$-cycle distance $\geq 2$ to vertex-disjoint triangles, and strengthening the conclusion from list flexibility to weighted DP-flexibility: \emph{Every simple planar graph without $4$-cycles and without intersecting triangles is weighted $\varepsilon$-flexibly DP-$4$-colorable.} The list size $4$ is sharp: Montassier, Raspaud, and Wang constructed a planar graph without $4$-cycles, $5$-cycles, and intersecting triangles that is not $3$-choosable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23647 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Flexible DP-4-coloring of planar graphs without 4-cycles and intersecting triangles Fang, Shu Liu, Runrun Yu, Gexin Combinatorics 05C15 Graph coloring with preferences offers a powerful framework for constraint satisfaction problems in which fulfilling every request is impossible but satisfying a guaranteed positive fraction is highly desirable. A \emph{request} on a graph $G$ equipped with a list assignment $L$ assigns to each vertex of some subset $dom(r)\subseteq V(G)$ a preferred color from its list. Following Dvořák, Norin, and Postle (2019), $G$ is \emph{$\varepsilon$-flexibly $k$-choosable} if, for every $k$-list assignment $L$ and every request $r$, there is an $L$-coloring of $G$ that agrees with $r$ on at least $\varepsilon|dom(r)|$ vertices. The corresponding notion for DP-coloring (correspondence coloring) was formalized by Bradshaw, Choi, and Kostochka (2025). Choi, Clemen, Ferrara, Horn, Ma, and Masařík (2022) proved that every planar graph without $4$-cycles and with $3$-cycle distance at least $2$ is $\varepsilon$-flexibly $4$-choosable. We improve the result in two respects: weakening the hypothesis from $3$-cycle distance $\geq 2$ to vertex-disjoint triangles, and strengthening the conclusion from list flexibility to weighted DP-flexibility: \emph{Every simple planar graph without $4$-cycles and without intersecting triangles is weighted $\varepsilon$-flexibly DP-$4$-colorable.} The list size $4$ is sharp: Montassier, Raspaud, and Wang constructed a planar graph without $4$-cycles, $5$-cycles, and intersecting triangles that is not $3$-choosable. |
| title | Flexible DP-4-coloring of planar graphs without 4-cycles and intersecting triangles |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2605.23647 |