A Note on 3-choosability of Planar Graphs Related to Montanssier’s Conjecture

Zhang, Haihui

Canadian mathematical bulletin, Tome 59 (2016) no. 2, pp. 440-448

Résumé

For a given list assignment $L\,=\,\{L\left( v \right)\,:\,v\,\in \,V\left( G \right)\}$ , a graph $G\,=\,\left( V,\,E \right)$ is $L$ -colorable if there exists a proper coloring $c$ of $G$ such that $c\left( v \right)\,\in \,L\left( v \right)$ for all $v\,\in \,V$ . If $G$ is $L$ -colorable for every list assignment $L$ having $\left| L\left( v \right) \right|\,\ge \,k$ for all $v\,\in \,V$ , then $G$ is said to be $k$ -choosable. Montassier (Inform. Process. Lett. 99 (2006) 68-71) conjectured that every planar graph without cycles of length 4, 5, 6, is 3-choosable. In this paper, we prove that every planar graph without 5-, 6- and 10-cycles, and without two triangles at distance less than 3 is 3-choosable.

Détail

DOI : 10.4153/CMB-2015-040-0

Mots-clés : 05C15, choosability, planar graph, cycle

Bibliographie

[1] [1] Alonand, N. Tarsi, M., Colorings and orientations of graphs.Combinatorica 12(1992), no. 2, 125–134. Google Scholar | DOI

[2] [2] Chen, M., Montassier, M., and Raspaud, A., Some structural properties of planar graphs and their applications to 3-choosability. Discrete Math. 312(2012), no. 2, 362–373. Google Scholar | DOI

[3] [3] Dvorak, Z., 3-choosabiliy of planar graphs with (<4)-cycles far apart. J. Combin. Theory Ser. B 104(2014) 28–59. Google Scholar | DOI

[4] [4] Dvorak, Z., Lidicky, B., and Skrekovski, R., Planar graphs without 3-, 7-, and 8-cycles are 3-choosable. Discrete Math.309(2009), no. 20, 5899–5904. Google Scholar | DOI

[5] [5] Erdos, P., Rubin, A. L., and Taylor, H., Choosability in graphs. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress.Numer., 26, Utilitas Math, Winnipeg, MB, 1980, pp. 125–157. Google Scholar

[6] [6] Farzad, B., Planar graphs without 7 -cycles are 4-choosable. SIAM J. Discrete Math.23(2009), no. 3. 1179–1199. Google Scholar | DOI

[7] [7] Fijavz, G., Juvan, M., Mohar, B., and Skrekovski, R., Planar graphs without cycles of specific lengths. Europ. J. Combin. 23(2002), no. 4, 377–388. Google Scholar | DOI

[8] [8] Gutner, S., The complexity ofplanar graph choosability. Discrete Math. 159(1996), no. 1-3, 119–130. Google Scholar | DOI

[9] [9] Lam, P. C. B., Xu, B., and Liu, J., The 4-choosability of plane graphs without 4-cycles. J. Combin. Theory Ser. B 76(1999), no. 1, 117–126. Google Scholar | DOI

[10] [10] Lam, P. C. B., Shiu, W., and Xu, B., On structure of some plane graphs with application to choosability. J. Combin. Theory Ser B, 82(2001), no. 2, 285–297. Google Scholar | DOI

[11] [11] Lam, P. C. B. Shiu, W., and Song, Z., The 3-choosability of plane graphs of girth 4. Discrete Math. 294(2005), no. 3, 297–301. Google Scholar | DOI

[12] [12] Lovasz, L., Combinatorial problems and exercises. North-Holland Publishing Co., Amsterdam-New York, 1979. Google Scholar

[13] [13] Mirzakhani, M., A small non-4-choosableplanar graph. Bull. Inst. Combin. Appl. 17(1996), 15–18. Google Scholar

[14] [14] Montassier, M., Raspaud, A., and Wang, W., Bordeaux 3-color conjecture and 3-choosability. Discrete Math. 306(2006), no. 6, 573–579. Google Scholar | DOI

[15] [15] Montassier, M., A note on the not 3-choosability of some families of planar graphs. Inform. Process. Lett. 99(2006), no. 2, 68–71. Google Scholar | DOI

[16] [16] Thomassen, C., Every planar graph is 5-choosable. J. Combin. Theory Ser. B 62(1994), no. 1, 180–181. Google Scholar | DOI

[17] [17] Thomassen, C. ,3-list-coloringplanar graph of girth 5.J. Combin. Theory, Ser. B 64(1995), no. 1, 101–107. Google Scholar | DOI

[18] [18] Voigt, M., List colourings of planar graphs. Discrete Math. 120(1993), no. 1-3, 215–219. Google Scholar | DOI

[19] [19] Voigt, M., A not 3-choosable planar graph without 3-cycles. Discrete Math. 146( 1995), no. 1-3, 325–328. Google Scholar | DOI

[20] [20] Wang, W.-F., Planar graphs that have no short cycles with a chord are 3-choosable. Taiwanese J. Math. 11(2007), no. 1, 179–186. Google Scholar

[21] [21] Wang, W. and Lih, K.-W, Choosability and edge choosability of planar graphs without five cycles.Appl. Math.Lett. 15(2002), no. 5, 561–565. Google Scholar | DOI

[22] [22] Wang, W., Choosability and edge choosability of planar graph without intersecting triangles.SIAM J. Discrete Math. 15(2002), no. 4, 538–545. Google Scholar | DOI

[23] [23] Wang, Y., Lu, H., and Chen, M., A note on 3-choosability of planar graphs.Inform. Process.Lett. 105(2008), no. 5, 206–211. Google Scholar | DOI

[24] [24] Xu, B., (4m, m)-choosability of plane graphs. J. Syst. Sci. Complex. 14(2001), no. 2, 174–178. Google Scholar

[25] [25] Zhang, H., Xu, B., andZ. Sun, Every plane graph with girth at least 4 without 8-and 9-circuits is 3-choosable. ArsCombin. 80(2006), 247–257. Google Scholar