Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
toroidal graph; defective choosability; chord
toroidal graph; defective choosability; chord
Summary:
A graph $G$ is called $(k,d)^*$-choosable if for every list assignment $L$ satisfying $|L(v)|= k$ for all $v\in V(G)$, there is an $L$-coloring of $G$ such that each vertex of $G$ has at most $d$ neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is $(4,1)^*$-choosable.
References:
[1] Chen Y., Zhu W., Wang W.: Improper choosability of graphs of nonnegative characteristic. Comput. Math. Appl. 56 (2008), 2073–2078. DOI 10.1016/j.camwa.2008.03.036 | MR 2466712 | Zbl 1165.05342
[2] Cushing W., Kierstead H.A.: Planar graphs are $1$-relaxed, $4$-choosable. European J. Combin. 31 (2009), 1385–1397. DOI 10.1016/j.ejc.2009.11.013 | MR 2644426 | Zbl 1221.05077
[3] Eaton N., Hull T.: Defective list colorings of planar graphs. Bull. Inst. Comb. Appl. 25 (1999), 79–87. MR 1668108 | Zbl 0916.05026
[4] Lih K., Song Z., Wang W., Zhang K.: A note on list improper coloring planar graphs. Appl. Math. Lett. 14 (2001), 269–273. DOI 10.1016/S0893-9659(00)00147-6 | MR 1820611 | Zbl 0978.05029
[5] Škrekovski R.: List improper colorings of planar graphs. Comb. Prob. Comp. 8 (1999), 293–299. DOI 10.1017/S0963548399003752 | MR 1702609 | Zbl 0940.05027
[6] Škrekovski R.: A Grötzsch-type theorem for list colorings with impropriety one. Comb. Prob. Comp. 8 (1999), 493–507. DOI 10.1017/S096354839900396X | MR 1731984
[7] Škrekovski R.: List improper colorings of planar graphs with prescribed girth. Discrete Math. 214 (2000), 221–233. DOI 10.1016/S0012-365X(99)00145-4 | MR 1743637 | Zbl 0940.05027
[8] Dong W., Xu B.: A note on list improper coloring of plane graphs. Discrete Appl. Math. 28 (2009), 433–436. DOI 10.1016/j.dam.2008.06.023 | MR 2479819 | Zbl 1209.05076
[9] Xu B., Zhang H.: Every toroidal graph without adjacent triangles is $(4,1)^*$-choosable. Discrete Appl. Math. 155 (2007), 74–78. DOI 10.1016/j.dam.2006.04.042 | MR 2281358 | Zbl 1107.05039
[10] Zhang L.: A $(3,1)^*$-choosable theorem on toroidal graphs. Discrete Appl. Math. 160 (2012), 332–338. DOI 10.1016/j.dam.2011.10.019 | MR 2862339 | Zbl 1241.05037
Search
Partner of
