On Sufficient Conditions for Planar Graphs to be 5-Flexible

被引:0
作者
Yang, Fan [1 ]
机构
[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
关键词
Planar graph; Reducible; Discharging; Flexibility; Satisfiable; 4-CYCLES;
D O I
10.1007/s00373-022-02480-4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, we study the flexibility of two planar graph classes H-1, H-2, where H-1, 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 G is an element of H-1 or G is an element of 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.
引用
收藏
页数:15
相关论文
共 50 条
  • [21] A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable
    Cai, Jian Sheng
    Teng, Chang Chun
    Yan, Gui Ying
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2014, 30 (06) : 993 - 1006
  • [22] Flexible list colorings in graphs with special degeneracy conditions
    Bradshaw, Peter
    Masarik, Tomas
    Stacho, Ladislav
    JOURNAL OF GRAPH THEORY, 2022, 101 (04) : 717 - 745
  • [23] Embedding planar 5-graphs in three pages
    Guan, Xiaxia
    Yang, Weihua
    DISCRETE APPLIED MATHEMATICS, 2020, 282 (282) : 108 - 121
  • [24] Some sufficient conditions for a planar graph of maximum degree six to be Class 1
    Bu, Yuehua
    Wang, Weifan
    DISCRETE MATHEMATICS, 2006, 306 (13) : 1440 - 1445
  • [25] Two sufficient conditions for a planar graph to be list vertex-2-arborable
    Wang, Yiqiao
    Yang, Yanping
    Huang, Danjun
    Wang, Weifan
    DISCRETE MATHEMATICS, 2022, 345 (06)
  • [26] The linear arboricity of planar graphs with maximum degree at least 5
    Chen, Hong-Yu
    Qi, Jian-Ming
    INFORMATION PROCESSING LETTERS, 2012, 112 (20) : 767 - 771
  • [27] Acyclic edge coloring of planar graphs with girth at least 5
    Hou, Jianfeng
    Wang, Weitao
    Zhang, Xiaoran
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 2958 - 2967
  • [28] 2-Distance coloring of planar graphs with girth 5
    Wei Dong
    Baogang Xu
    Journal of Combinatorial Optimization, 2017, 34 : 1302 - 1322
  • [29] LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g >= 5
    Bu, Yuehua
    Yang, Sheng
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (01)
  • [30] 2-Distance coloring of planar graphs with girth 5
    Dong, Wei
    Xu, Baogang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (04) : 1302 - 1322