On sufficient conditions for planar graphs to be 5-flexible

DOI10.1007/S00373-022-02480-4zbMATH Open1485.05070OpenAlexW4220836813MaRDI QIDQ2117537FDOQ2117537

Authors: Yanyan Li 

Publication date: 21 March 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: In this paper, we study the flexibility of two planar graph classes $mathcal{H}_1$, $mathcal{H}_2$, where $mathcal{H}_1$, $mathcal{H}_2$ denote the set of all hopper-free planar graphs and house-free planar graphs, respectively. 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 $Ginmathcal{H}_1$ or $Ginmathcal{H}_2$ such that all lists have size at least $5$, then there exists an $L$-coloring respecting at least a constant fraction of the preferences.

Full work available at URL: https://arxiv.org/abs/2202.12706

Recommendations

• Flexibility of planar graphs of girth at least six
• Flexibility of triangle‐free planar graphs
• Flexibility of planar graphs -- sharpening the tools to get lists of size four
• On weak flexibility in planar graphs
• Flexible list colorings in graphs with special degeneracy conditions

zbMATH Keywords

planar graphflexibilitydischarginghopper-free graphhouse-free graphreducible subgraph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory with applications
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• A short list color proof of Grötzsch's theorem
• Triangle-free planar graphs with the smallest independence number
• A non-3-choosable planar graph without cycles of length 4 and 5
• The 4-choosability of plane graphs without 4-cycles
• Planar graphs without triangular 4-cycles are 3-choosable
• Choosability and Edge Choosability of Planar Graphs without Intersecting Triangles
• Planar graphs without 4-cycles adjacent to triangles are 4-choosable
• Flexibility of planar graphs -- sharpening the tools to get lists of size four
• List coloring with requests

Cited In (6)

• Flexibility of planar graphs without 4-cycles
• Flexible list colorings: maximizing the number of requests satisfied
• On weak flexibility in planar graphs
• Flexibility of planar graphs of girth at least six
• Flexible coloring of graphs
• Flexibility of triangle‐free planar graphs

This page was built for publication: On sufficient conditions for planar graphs to be 5-flexible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117537)