×

zbMATH — the first resource for mathematics

Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable. (English) Zbl 1283.05182
Summary: A graph \(G\) is \((a,b)\)-choosable if for any color list of size \(a\) associated with each vertex, one can choose a subset of \(b\) colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer \(m\geq 1\), every finite triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable.

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C22 Signed and weighted graphs
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Tuza, Zs.; Voigt, M., Choosability and fractional chromatic number, Discrete Math., 165-166, 31-38, (1997) · Zbl 0877.05020
[2] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and List colourings of multigraph, J. Combin. Theory Ser. B, 71, 184-204, (1997) · Zbl 0876.05032
[3] Cropper, M. M.; Goldwasser, J. L.; Hilton, A. J.W.; Hoffman, D. G.; Johnson, P. D., Extending the disjoint-representatives theorems of Hall, halmos, and vaughan to List-multicolorings of graphs, J. Graph Theory, 33, 4, 199-219, (2000) · Zbl 0944.05040
[4] Erdős, P.; Rubin, A. L; Taylor, H., Choosability in graphs, (Proc. West-Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. XXVI, (1979)), 125-157
[5] J.-C. Godin, Coloration et choisissabilité des graphes et applications, Ph.D. Thesis, Université du Sud Toulon-Var, France, 2009 (in French).
[6] Gravier, S., A hajós-like theorem for List coloring, Discrete Math., 152, 299-302, (1996) · Zbl 0853.05037
[7] Gutner, S.; Tarsi, M., Some results on \((a : b)\)-choosability, Discrete Math., 309, 2260-2270, (2009) · Zbl 1198.05049
[8] Havet, F., Channel assignment and multicolouring of the induced subgraphs of the triangular lattice, Discrete Math., 233, 219-233, (2001) · Zbl 0983.05031
[9] Havet, F., Choosability of the square of planar subcubic graphs with large girth, Discrete Math., 309, 3553-3563, (2009) · Zbl 1213.05084
[10] Havet, F.; Zerovnik, J., Finding a five bicolouring of a triangle-free subgraph of the triangular lattice, Discrete Math., 244, 103-108, (2002) · Zbl 0997.05033
[11] Kchikech, M.; Togni, O., Approximation algorithms for multicoloring powers of square and triangular meshes, Discrete Math. Theor. Comput. Sci., 8, 1, 159-172, (2006) · Zbl 1153.05026
[12] McDiarmid, C.; Reed, B., Channel assignment and weighted coloring, Networks, 36, 114-117, (2000) · Zbl 0971.90100
[13] Sudeep, K. S.; Vishwanathan, S., A technique for multicoloring triangle-free hexagonal graphs, Discrete Math., 300, 256-259, (2005) · Zbl 1076.05037
[14] Thomassen, C., The chromatic number of a graph of girth 5 on a fixed surface, J. Combin. Theory, 38-71, (2003) · Zbl 1020.05030
[15] Tuza, Zs.; Voigt, M., Every 2-choosable graph is \((2 m, m)\)-choosable, J. Graph Theory, 22, 245-252, (1996) · Zbl 0853.05034
[16] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, in: Diskret. Analiz., No. 29, Metody Diskret. Anal. v Teorii Kodov i Shem 101 (1976) 3-10 (in Russian).
[17] Voigt, M., Choosability of planar graphs, Discrete Math., 150, 457-460, (1996) · Zbl 0852.05048
[18] M. Voigt, On list colourings and choosability of graphs, in: Abilitationsschrift, TU Ilmenau, 1998.
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.