×

zbMATH — the first resource for mathematics

List injective colorings of planar graphs. (English) Zbl 1216.05027
Summary: A vertex coloring of a graph \(G\) is called injective if any two vertices joined by a path of length two get different colors. A graph \(G\) is injectively \(k\)-choosable if any list \(L\) of admissible colors on \(V(G)\) of size \(k\) allows an injective coloring \(\varphi\) such that \(\varphi(v)\in L(v)\) whenever \(v\in V(G)\). The least \(k\) for which \(G\) is injectively \(k\)-choosable is denoted by \(\chi^l_i(G)\).
Note that \(\chi^l_i\geq \Delta\) for every graph with maximum degree \(\Delta\). For planar graphs with girth \(g\), Y. Bu, D. Chen, A. Raspaud and W. Wang [Discrete Appl. Math. 157, No. 4, 663–672 (2009; Zbl 1173.05320)] proved that \(\chi^l_i= \Delta\) if \(\Delta\geq 71\) and \(g\geq> 7\), which we strengthen here to \(\Delta\geq 16\). On the other hand, there exist planar graphs with \(g= 6\) and \(\chi^l_i= \Delta+ 1\) for any \(\Delta\geq 2\). D. W. Cranston, S.-J. Kim and G. Yu [Discrete Math. 310, No. 21, 2965–2973 (2010; Zbl 1209.05075)] proved that \(\chi^l_i\leq\Delta+ 1\) if \(g\geq 9\) and \(\Delta\geq 4\). We prove that each planar graph with \(g\geq 6\) and \(\Delta\geq 24\) has \(\chi^l_i\leq\Delta+ 1\).

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agnarsson, G.; Halldórsson, M.M., Coloring powers of planar graphs, (), 654-662 · Zbl 0965.05042
[2] Agnarsson, G.; Halldórsson, M.M., Coloring powers of planar graphs, SIAM J. discrete math., 16, 4, 651-662, (2003) · Zbl 1029.05047
[3] Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[4] Borodin, O.V.; Broersma, H.J.; Glebov, A.; van den Heuvel, J., The structure of plane triangulations in terms of clusters and stars, Diskretn. anal. issled. oper. ser. 1, 8, 2, 15-39, (2001), (in Russian) · Zbl 0977.05036
[5] Borodin, O.V.; Broersma, H.J.; Glebov, A.; van den Heuvel, J., Minimal degrees and chromatic numbers of squares of planar graphs, Diskretn. anal. issled. oper. ser. 1, 8, 4, 9-33, (2001), (in Russian) · Zbl 1012.05074
[6] Borodin, O.V.; Glebov, A.N.; Ivanova, A.O.; Neustroeva, T.K.; Tashkinov, V.A., Sufficient conditions for the 2-distance \((\Delta + 1)\)-colorability of plane graphs, Sib. elektron. mat. izv., 1, 129-141, (2004), (in Russian) · Zbl 1076.05032
[7] Borodin, O.V.; Ivanova, A.O., List 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth 6, European J. combin., 30, 1257-1262, (2009) · Zbl 1190.05055
[8] Borodin, O.V.; Ivanova, A.O., List 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth 6 and \(\Delta \geq 24\), Sibirsk. mat. zh., 6, 1216-1224, (2009), (in Russian) · Zbl 1224.05159
[9] Borodin, O.V.; Ivanova, A.O., 2-distance \((\Delta + 2)\)-coloring of planar graphs with girth six and \(\Delta \geq 18\), Discrete math., 309, 6496-6502, (2009) · Zbl 1184.05040
[10] Borodin, O.V.; Ivanova, A.O.; Neustroeva, T.K., Sufficient conditions for the 2-distance (\(\Delta + 1\))-colorability of plane graphs, Sib. elektron. mat. izv., 1, 76-90, (2004) · Zbl 1077.05040
[11] Borodin, O.V.; Ivanova, A.O.; Neustroeva, T.K., List 2-distance \((\Delta + 1)\)-coloring of planar graphs with given girth, Diskretn. anal. issled. oper. ser. 1, 14, 3, 13-30, (2007), (in Russian) · Zbl 1249.05114
[12] Borodin, O.V.; Ivanova, A.O.; Neustroeva, T.K., Sufficient conditions for 2-distance (\(\Delta + 1\))-colorability of planar graphs of girth 6, Diskretn. anal. issled. oper. ser. 1, 12, 3, 32-47, (2005), (in Russian) · Zbl 1249.05113
[13] Borodin, O.V.; Ivanova, A.O.; Neustroeva, T.K., Sufficient conditions for the minimum 2-distance colorability of plane graphs with girth six, Sib. elektron. mat. izv., 3, 441-450, (2006), (in Russian) · Zbl 1119.05039
[14] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., List edge and List total colourings of multigraphs, J. combin. theory ser. B, 71, 2, 184-204, (1997) · Zbl 0876.05032
[15] Bu, Y.; Chen, D.; Raspaud, A.; Wang, W., Injective coloring of planar graphs, Discrete appl. math., 157, 4, 663-672, (2009) · Zbl 1173.05320
[16] D.W. Cranston, S.-J. Kim, G. Yu, Injective colorings of sparse graphs (submitted for publication). · Zbl 1209.05075
[17] Dvořák, Z.; Král’, D.; Nejedlý, P.; Škrekovski, R., Coloring squares of planar graphs with girth six, European J. combin., 29, 4, 838-849, (2008) · Zbl 1143.05027
[18] Hahn, G.; Kratochvíl, J.; Širáň, J.; Sotteau, D., On the injective chromatic number of graphs, Discrete math., 256, 1-2, 179-192, (2002) · Zbl 1007.05046
[19] He, W.; Hou, X.; Lih, K.W.; Shao, J.; Wang, W.; Zhu, X., Edge-partitions of planar graphs and their game coloring numbers, J. graph theory, 41, 307-317, (2002) · Zbl 1016.05033
[20] Ivanova, A.O., List 2-distance \((\Delta + 1)\)-coloring of planar graphs with girth at least 7, Diskretn. anal. issled. oper., 17, 5, 22-36, (2010), (in Russian) · Zbl 1249.05118
[21] Lužar, B.; Škrekovski, R.; Tancer, M., Injective colorings of planar graphs with few colors, Discrete math., 309, 18, 5636-5649, (2009) · Zbl 1209.05093
[22] Molloy, M.; Salavatipour, M.R., Frequency channel assignment on planar networks, (), 736-747 · Zbl 1040.90034
[23] Molloy, M.; Salavatipour, M.R., A bound on the chromatic number of the square of a planar graph, J. combin. theory ser. B., 94, 189-213, (2005) · Zbl 1071.05036
[24] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany, 1977.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.