×

Improper choosability of graphs of nonnegative characteristic. (English) Zbl 1165.05342

Summary: A graph \(G\) is called \((k,d)^{*}\)-choosable if, for every list assignment \(L\) with |\(L(v)|=k\) for all \(v\in V(G)\), there is an \(L\)-coloring of \(G\) such that every vertex has at most \(d\) neighbors having the same color as itself.Let \(G\) be a graph embeddable in a surface of nonnegative characteristic.
We prove: (1) If \(G\) contains no \(k\)-cycle with a chord for all \(k=4,5,6\), then \(G\) is \((3,1)^{*}\)-choosable; (2) If \(G\) contains neither 5-cycle with a chord nor 6-cycle with a chord, then \(G\) is \((4,1)^{*}\)-choosable.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1979)
[2] Vizing, V. G., Vertex coloring with given colors, Diskret. Analiz., 29, 3-10 (1976), (in Russian) · Zbl 1249.90303
[3] Borowiecki, M.; Broere, I.; Frick, M.; Mihók, P.; Semanišin, G., A survey of hereditary properties of graphs, Discuss. Math. Graph Theory, 17, 5-55 (1997) · Zbl 0902.05026
[4] Borowiecki, M.; Drgas-Burchardt; Mihók, P., Generalized list colourings of graphs, Discuss. Math. Graph Theory, 15, 185-193 (1995) · Zbl 0845.05046
[5] Škrekovski, R., List improper colorings of planar graphs, Combin. Probab. Comput., 8, 293-299 (1999) · Zbl 0940.05031
[6] Eaton, N.; Hull, H., Defective list colorings of planar graphs, Bull. Inst. Combin. Appl., 25, 79-87 (1999) · Zbl 0916.05026
[7] Škrekovski, R., A Grötzsch-type theorem for list colorings with impropriety one, Combin. Probab. Comput., 8, 493-507 (2000) · Zbl 0941.05027
[8] Škrekovski, R., List improper colorings of planar graphs with prescribed girth, Discrete Math., 214, 221-233 (2000) · Zbl 0940.05027
[9] Lih, K.-W.; Song, Z.; Wang, W.; Zhang, K., A note on list improper coloring planar graphs, Appl. Math. Lett., 14, 269-273 (2001) · Zbl 0978.05029
[10] Böhme, T.; Mohar, B.; Stiebitz, M., Dirac’s map-color theorem for choosability, J. Graph Theory, 32, 327-339 (1999) · Zbl 0941.05025
[11] Xu, B.; Zhang, H., Every torodial graph without adjacent triangles is \((4, 1)^\ast \)-choosable, Discrete Appl. Math., 155, 74-78 (2007) · Zbl 1107.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.