Flexibility of planar graphs without 4-cycles

Abstract

Proper graph coloring assigns different colors to adjacent vertices ofthe graph. Usually, the number of colors is fixed or as small as possible. Considerapplications (e.g. variants of scheduling) where colors represent limited resourcesand graph represents conflicts, i.e., two adjacent vertices cannot obtain the sameresource. In such applications, it is common that some vertices have preferredresource(s). However, unfortunately, it is not usually possible to satisfy all suchpreferences. The notion called flexibility was recently defined in [Dvořák, Norin,Postle: List coloring with requests, Journal of Graph Theory 2019]. There insteadof satisfying all the preferences the aim is to satisfy at least a constant fraction ofthe request.
Recently, the structural properties of planar graphs in terms of flexibility wereinvestigated. We continue this line of research. Let G be a planar graph with a listassignment L. Suppose a preferred color is given for some of the vertices. We provethat if G is a planar graph without 4-cycles and all lists have size at least five, thenthere exists an L-coloring respecting at least a constant fraction of the preferences.