On sufficient conditions for planar graphs to be 5-flexible

DOI10.1007/S00373-022-02480-4MaRDI QIDQ2117537zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 March 2022

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

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

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)

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.

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

Cites work

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

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)