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 条
[41]   2-Distance coloring of planar graphs with maximum degree 5 [J].
Chen, Ming ;
Jiang, Lu ;
Wang, Min ;
Zhou, Shan .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (01)
[42]   Vertex arboricity of planar graphs without intersecting 5-cycles [J].
Cai, Hua ;
Wu, Jianliang ;
Sun, Lin .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) :365-372
[43]   Acyclic edge coloring of planar graphs without 5-cycles [J].
Shu, Qiaojun ;
Wang, Weifan ;
Wang, Yiqiao .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) :1211-1223
[44]   Flexibility of planar graphs of girth at least six [J].
Dvorak, Zdenek ;
Masarik, Tomas ;
Musilek, Jan ;
Pangrac, Ondrej .
JOURNAL OF GRAPH THEORY, 2020, 95 (03) :457-466
[45]   Planar domination graphs [J].
Eschen, EM ;
Klostermeyer, WF ;
Sritharan, R .
DISCRETE MATHEMATICS, 2003, 268 (1-3) :129-137
[46]   On the reconstruction of planar graphs [J].
Bilinski, Mark ;
Kwon, Young Soo ;
Yu, Xingxing .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) :745-756
[47]   Drawing Planar Graphs [J].
Rahman, Md Saidur ;
Karim, Md Rezaul .
WALCOM: ALGORITHMS AND COMPUTATION (WALCOM 2020), 2020, 12049 :3-14
[48]   Decomposing planar graphs into graphs with degree restrictions [J].
Cho, Eun-Kyung ;
Choi, Ilkyoo ;
Kim, Ringi ;
Park, Boram ;
Shan, Tingting ;
Zhu, Xuding .
JOURNAL OF GRAPH THEORY, 2022, 101 (02) :165-181
[49]   LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH [J].
Hudak, Peter ;
Macekova, Maria ;
Madaras, Tomas ;
Siroczki, Pavol .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) :227-238
[50]   Weak degeneracy of line graphs of planar graphs [J].
Xu, Ningyan ;
Zuo, Qian .
DISCRETE MATHEMATICS, 2025, 348 (12)