Flexible List Colorings in Graphs with Special Degeneracy Conditions

Speaker(s)

Tomáš Masařík

Affiliation

Simon Fraser University

Date

April 15, 2021, 12:15 p.m.

Information about the event

online

Seminar

Seminar Algorithms

---

For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020]. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable.

---