Flexibility of planar graphs without 4-cycles
From MaRDI portal
Publication:6315035
arXiv1903.01460MaRDI QIDQ6315035FDOQ6315035
Authors: Tomáš Masařík 
Publication date: 4 March 2019
Abstract: Proper graph coloring assigns different colors to adjacent vertices of the graph. Usually, the number of colors is fixed or as small as possible. Consider applications (e.g. variants of scheduling) where colors represent limited resources and graph represents conflicts, i.e., two adjacent vertices cannot obtain the same resource. In such applications, it is common that some vertices have preferred resource(s). However, unfortunately, it is not usually possible to satisfy all such preferences. The notion called flexibility was recently defined in [Dvov{r}'ak, Norin, Postle: List coloring with requests, Journal of Graph Theory 2019]. There instead of satisfying all the preferences the aim is to satisfy at least a constant fraction of the request. Recently, the structural properties of planar graphs in terms of flexibility were investigated. We continue this line of research. Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G is a planar graph without 4-cycles and all lists have size at least five, then there exists an L-coloring respecting at least a constant fraction of the preferences.
This page was built for publication: Flexibility of planar graphs without 4-cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315035)
