Back to Search Start Over

Flexible list colorings: Maximizing the number of requests satisfied.

Flexible list colorings: Maximizing the number of requests satisfied.

Authors :
Kaul, Hemanshu
Mathew, Rogers
Mudrock, Jeffrey A.
Pelsmajer, Michael J.
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

Subjects :
*BIPARTITE graphs
*COLORING matter

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