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 条
[31]   Sufficient conditions for a planar graph to be list edge Δ-colorable and list totally (Δ+1)-colorable [J].
Lu, Qiuli ;
Miao, Zhengke ;
Wang, Yingqian .
DISCRETE MATHEMATICS, 2013, 313 (05) :575-580
[32]   Largest planar graphs and largest maximal planar graphs of diameter two [J].
Yang, YS ;
Lin, JH ;
Dai, YJ .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2002, 144 (1-2) :349-358
[33]   Acyclic 5-choosability of planar graphs without small cycles [J].
Montassier, Mickael ;
Raspaud, Andre ;
Wang, Weifan .
JOURNAL OF GRAPH THEORY, 2007, 54 (03) :245-260
[34]   Total colorings of planar graphs without intersecting 5-cycles [J].
Wang, Bing ;
Wu, Jian-Liang .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) :1815-1821
[35]   Total colorings of planar graphs without adjacent 5-cycles [J].
Chang, Jian ;
Wang, Hui-Juan .
ARS COMBINATORIA, 2019, 142 :329-344
[36]   Vertex arboricity of planar graphs without intersecting 5-cycles [J].
Hua Cai ;
Jianliang Wu ;
Lin Sun .
Journal of Combinatorial Optimization, 2018, 35 :365-372
[37]   2-distance coloring of planar graphs with maximum degree 5 [J].
Chen, Ming ;
Miao, Lianying ;
Zhou, Shan .
DISCRETE MATHEMATICS, 2022, 345 (04)
[38]   Planar graphs with girth at least 5 are (3,4)-colorable [J].
Choi, Ilkyoo ;
Yu, Gexin ;
Zhang, Xia .
DISCRETE MATHEMATICS, 2019, 342 (12)
[39]   List injective coloring of planar graphs with disjoint 5--cycles [J].
Li, Wenwen ;
Cai, Jiansheng .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (04)
[40]   The Linear Arboricity of Planar Graphs without 5-Cycles with Chords [J].
Chen, Hong-Yu ;
Tan, Xiang ;
Wu, Jian-Liang .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2013, 36 (02) :285-290