(3, 1)<sup>*</sup>-choosability of plane graphs without adjacent single cycles

doi:10.3868/s140-DDD-024-0008-x

Front. Math. China

2024, Vol. 19

Issue (2) : 101-115 https://doi.org/10.3868/s140-DDD-024-0008-x

(3, 1)^*-choosability of plane graphs without adjacent single cycles

Jufeng ZHANG¹, Min CHEN¹(

), Yiqiao WANG²

¹. College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
². School of Management, Beijing University of Chinese Medicine, Beijing 100029, China

Download: PDF(785 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Given a list assignment of L to graph G, assign a list L(v) of colors to each $v ∈ V (G)$ . An (L, d)*-coloring is a mapping π that assigns a color π(v) $∈$ L(v) to each vertex v $∈$ V(G) such that at most d neighbors of v receive the color v. If there exists an (L, d)*-coloring for every list assignment L with $| L (v) | ⩾ k$ for all $v ∈ V (G)$ , then G is called to be (k, d)^*-choosable. In this paper, we prove every planar graph G without adjacent k-cycles is (3, 1)*-choosable, where k $∈$ {3, 4, 5}.

Keywords Plane graph improper list coloring (k, d)^*-choosable cycle

Corresponding Author(s): Min CHEN

Online First Date: 31 May 2024 Issue Date: 11 June 2024

Cite this article:

Jufeng ZHANG,Min CHEN,Yiqiao WANG. (3, 1)^*-choosability of plane graphs without adjacent single cycles[J]. Front. Math. China, 2024, 19(2): 101-115.

URL:

https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-024-0008-x
https://academic.hep.com.cn/fmc/EN/Y2024/V19/I2/101

Fig.1 Weight rransfer rules (R0)?(R4)

1	J A BondyU S R Murty. Graph Theory. Graduate Texts in Mathematics, Vol 244. New York: Springer, 2008
2	M Chen, A Raspaud. On (3, 1)*-choosability of planar graphs without adjacent short cycles. Discrete Appl Math 2014; 162: 159–166
3	M Chen, A Raspaud, W F Wang. A (3, 1)*-choosable theorem on planar graphs. J Comb Optim 2016; 32(3): 927–940
4	L J Cowen, R H Cowen, D R Woodall. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J Graph Theory 1986; 10(2): 187–195
5	W Cushing, H A Kierstead. Planar graphs are 1-relaxed, 4-choosable. European J Combin 2010; 31(5): 1385–1397
6	W Dong, B G Xu. A note on list improper coloring of plane graphs. Discrete Appl Math 2009; 157(2): 433–436
7	N Eaton, T Hull. Defective list colorings of planar graphs. Bull Inst Combin Appl 1999; 25: 79–87
8	K-W Lih, Z M Song, W F Wang, K M Zhang. A note on list improper coloring planar graphs. Appl Math Lett 2001; 14(3): 269–273
9	R Škrekovski. A Grötzsch-type theorem for list colourings with impropriety one. Combin Probab Comput 1999; 8(5): 493–507
10	C Thomassen. Every planar graph is 5-choosable. J Combin Theory Ser B 1994; 62(1): 180–181
11	M Voigt. List colourings of planar graphs. Discrete Math 1993; 120(1/2/3): 215–219
12	Y Q Wang, L J Xu. Improper choosability of planar graphs without 4-cycles. SIAM J Discrete Math 2013; 27(4): 2029–2037
13	B G Xu. On (3, 1)*-coloring of plane graphs. SIAM J. Discrete Math. 2008/2009; 23(1): 205–220
14	B G Xu, H H Zhang. Every toroidal graph without adjacent triangles is (4, 1)*-choosable. Discrete Appl Math 2007; 155(1): 74–78
15	L Zhang. A (3, 1)*-choosable theorem on toroidal graphs. Discrete Appl Math 2012; 160(3): 332–338

[1]	Linlin FU, Jiahao XU, Fan WU. New proof of continuity of Lyapunov exponents for a class of smooth Schrödinger cocycles with weak Liouville frequencies[J]. Front. Math. China, 2020, 15(3): 467-489.
[2]	Xie-Bin CHEN. Matchings extend to Hamiltonian cycles in hypercubes with faulty edges[J]. Front. Math. China, 2019, 14(6): 1117-1132.
[3]	Lei LIU. Lagrangian Grassmann manifold Λ(2)[J]. Front. Math. China, 2018, 13(2): 341-365.
[4]	Ruipu BAI,Ying LI. Extensions of n-Hom Lie algebras[J]. Front. Math. China, 2015, 10(3): 511-522.
[5]	Min ZHOU,Haitao CAO. Almost resolvable maximum packings of complete graphs with 5-cycles[J]. Front. Math. China, 2015, 10(2): 461-475.
[6]	Xie-Bin CHEN. Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges[J]. Front Math Chin, 2014, 9(1): 17-30.
[7]	Hao FAN, Guizhen LIU. Properties of Hamilton cycles of circuit graphs of matroids[J]. Front Math Chin, 2013, 8(4): 801-809.
[8]	Kai TAO. Continuity of Lyapunov exponent for analytic quasi-periodic cocycles on higher-dimensional torus[J]. Front Math Chin, 2012, 7(3): 521-542.
[9]	Yanhong BAO, Xianneng DU, Yu YE. Poisson structures on basic cycles[J]. Front Math Chin, 2012, 7(3): 385-396.
[10]	Linping PENG. Quadratic perturbations of a quadratic reversible center of genus one[J]. Front Math Chin, 2011, 6(5): 911-930.
[11]	Han REN, Ni CAO, . Finding short cycles in embedded graph in polynomial time[J]. Front. Math. China, 2010, 5(2): 319-327.
[12]	Xuanji HOU, . Stable one-dimensional quasi-periodic cocycles on unitary group[J]. Front. Math. China, 2009, 4(4): 651-658.
[13]	Huanxia FA, Xiaoyan ZHENG, Junbo LI, . Second Leibniz cohomology group of twisted N = 2 superconformal algebra[J]. Front. Math. China, 2009, 4(4): 627-635.
[14]	Jun-Ming XU, Meijie MA. Survey on path and cycle embedding in some networks[J]. Front Math Chin, 2009, 4(2): 217-252.
[15]	LI Junbo, SU Yucai. Leibniz central extension on centerless twisted Schr?dinger-Virasoro algebra[J]. Front. Math. China, 2008, 3(3): 337-344.

Viewed

Full text

Abstract

Cited

Shared

Discussed