Back to Search
Start Over
Flexible list colorings: Maximizing the number of requests satisfied.
Flexible list colorings: Maximizing the number of requests satisfied.
- Source :
-
Journal of Graph Theory . Oct2024, Vol. 106 Issue 4, p887-906. 20p. - Publication Year :
- 2024
-
Abstract
- Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose 0≤ϵ≤1, G is a graph, L is a list assignment for G, and r is a function with nonempty domain D⊆V(G) such that r(v)∈L(v) for each v∈D (r is called a request of L). The triple (G,L,r) is ϵ‐satisfiable if there exists a proper L‐coloring f of G such that f(v)=r(v) for at least ϵ∣D∣ vertices in D. We say G is (k,ϵ)‐flexible if (G,L′,r′) is ϵ‐satisfiable whenever L′ is a k‐assignment for G and r′ is a request of L′. It was shown by Dvořák et al. that if d+1 is prime, G is a d‐degenerate graph, and r is a request for G with domain of size 1, then (G,L,r) is 1‐satisfiable whenever L is a (d+1)‐assignment. In this paper, we extend this result to all d for bipartite d‐degenerate graphs. The literature on flexible list coloring tends to focus on showing that for a fixed graph G and k∈N there exists an ϵ>0 such that G is (k,ϵ)‐flexible, but it is natural to try to find the largest possible ϵ for which G is (k,ϵ)‐flexible. In this vein, we improve a result of Dvořák et al., by showing d‐degenerate graphs are (d+2,1∕2d+1)‐flexible. In pursuit of the largest ϵ for which a graph is (k,ϵ)‐flexible, we observe that a graph G is not (k,ϵ)‐flexible for any k if and only if ϵ>1∕ρ(G), where ρ(G) is the Hall ratio of G, and we initiate the study of the list flexibility number of a graphG, which is the smallest k such that G is (k,1∕ρ(G))‐flexible. We study relationships and connections between the list flexibility number, list chromatic number, list packing number, and degeneracy of a graph. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BIPARTITE graphs
*COLORING matter
Subjects
Details
- Language :
- English
- ISSN :
- 03649024
- Volume :
- 106
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 177904514
- Full Text :
- https://doi.org/10.1002/jgt.23103