| Title:
|
On $(4,1)^*$-choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles (English) |
| Author:
|
Zhang, Haihui |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
54 |
| Issue:
|
3 |
| Year:
|
2013 |
| Pages:
|
339-344 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
toroidal graph |
| Keyword:
|
defective choosability |
| Keyword:
|
chord |
| MSC:
|
05C15 |
| MSC:
|
05C78 |
| . |
| Date available:
|
2013-06-29T06:49:32Z |
| Last updated:
|
2015-10-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143305 |
| . |
| Reference:
|
[1] Chen Y., Zhu W., Wang W.: Improper choosability of graphs of nonnegative characteristic.Comput. Math. Appl. 56 (2008), 2073–2078. Zbl 1165.05342, MR 2466712, 10.1016/j.camwa.2008.03.036 |
| Reference:
|
[2] Cushing W., Kierstead H.A.: Planar graphs are $1$-relaxed, $4$-choosable.European J. Combin. 31 (2009), 1385–1397. Zbl 1221.05077, MR 2644426, 10.1016/j.ejc.2009.11.013 |
| Reference:
|
[3] Eaton N., Hull T.: Defective list colorings of planar graphs.Bull. Inst. Comb. Appl. 25 (1999), 79–87. Zbl 0916.05026, MR 1668108 |
| Reference:
|
[4] Lih K., Song Z., Wang W., Zhang K.: A note on list improper coloring planar graphs.Appl. Math. Lett. 14 (2001), 269–273. Zbl 0978.05029, MR 1820611, 10.1016/S0893-9659(00)00147-6 |
| Reference:
|
[5] Škrekovski R.: List improper colorings of planar graphs.Comb. Prob. Comp. 8 (1999), 293–299. Zbl 0940.05027, MR 1702609, 10.1017/S0963548399003752 |
| Reference:
|
[6] Škrekovski R.: A Grötzsch-type theorem for list colorings with impropriety one.Comb. Prob. Comp. 8 (1999), 493–507. MR 1731984, 10.1017/S096354839900396X |
| Reference:
|
[7] Škrekovski R.: List improper colorings of planar graphs with prescribed girth.Discrete Math. 214 (2000), 221–233. Zbl 0940.05027, MR 1743637, 10.1016/S0012-365X(99)00145-4 |
| Reference:
|
[8] Dong W., Xu B.: A note on list improper coloring of plane graphs.Discrete Appl. Math. 28 (2009), 433–436. Zbl 1209.05076, MR 2479819, 10.1016/j.dam.2008.06.023 |
| Reference:
|
[9] Xu B., Zhang H.: Every toroidal graph without adjacent triangles is $(4,1)^*$-choosable.Discrete Appl. Math. 155 (2007), 74–78. Zbl 1107.05039, MR 2281358, 10.1016/j.dam.2006.04.042 |
| Reference:
|
[10] Zhang L.: A $(3,1)^*$-choosable theorem on toroidal graphs.Discrete Appl. Math. 160 (2012), 332–338. Zbl 1241.05037, MR 2862339, 10.1016/j.dam.2011.10.019 |
| . |
