Chromatic number of graphs with special distance sets, I

Venkataraman Yegnanarayanan

Algebra and discrete mathematics, Tome 17 (2014) no. 1, pp. 135-160.

Résumé

Given a subset $D$ of positive integers, an integer distance graph is a graph $G(\mathbb{Z}, D)$ with the set $\mathbb{Z}$ of integers as vertex set and with an edge joining two vertices $u$ and $v$ if and only if $|u - v| \in D$. In this paper we consider the problem of determining the chromatic number of certain integer distance graphs $G(\mathbb{Z}, D)$whose distance set $D$ is either 1) a set of $(n+1)$ positive integers for which the $n^{th}$ power of the last is the sum of the $n^{th}$ powers of the previous terms, or 2) a set of pythagorean quadruples, or 3) a set of pythagorean $n$-tuples, or 4) a set of square distances, or 5) a set of abundant numbers or deficient numbers or carmichael numbers, or 6) a set of polytopic numbers, or 7) a set of happy numbers or lucky numbers, or 8) a set of Lucas numbers, or 9) a set of $\mathcal{U}$lam numbers, or 10) a set of weird numbers. Besides finding the chromatic number of a few specific distance graphs we also give useful upper and lower bounds for general cases. Further, we raise some open problems.

Détail

Keywords: chromatic number, prime distance graph, unit distance graph.

Bibliographie

[1] Balaban, A. T., “Highly discriminating distance-based topological index”, Chem. Phys. Lett., 89 (1982), 399–404 | DOI | MR

[2] Benda, M, Perles, A., “Colorings of metric spaces”, Geombinatorics, 9 (2000), 113–126 | MR | Zbl

[3] de Bruijn, N. G. and Erdos, P., “A color problem for infinite graphs and a problem in the theory of relations”, Proceedings, Series A, 54:5; Indag. Math., 13:5 (1951)

[4] Eggleton, R. B., Erdös, P., Skilton, D. K., “Colouring prime distance graphs”, Graphs and Combinatorics, 6 (1990), 17–32 | DOI | MR | Zbl

[5] Eggleton, R.B, Erdös, P, Skilton, D. K., “Coloring the real line”, J. Combin. Theory Ser. B, 73 (1985), 86–100 | DOI | MR

[6] Elk, S. B., “Canonical orderings of hexagons that: (1) nearly meet the intent of Patterson's nomenclature rules and (2) orient a molecule for purposes of assigning a IUPAC name”, Polycyclic Aromat. Comp., 1 (1990), 109–121 | DOI

[7] Elk, S. B. A., “Canonical ordering of polybenzenes and polymantanes using prime number factorization technique”, J. Math. Chem., 4 (1990), 55–68 | DOI | MR

[8] Elk, S. B., “Graph theoretical algorithm to canonically name the isomers of the regular polyhedranes”, J. Chem. Inf. Comput. Sci., 32 (1992), 14–22 | DOI

[9] Falconer, K. J., “The realization of distances in measurable subsets covering $R^{n}$”, J. of Combinatorial Theory Ser. A, 31:2 (1981), 184–189 | DOI | MR | Zbl

[10] Frankl, P., Wilson, R. M., “Intersection theorems with geometric consequences”, Combinatorica, 1 (1981), 357–368 | DOI | MR | Zbl

[11] Fiuredi, Z., Kang, J-H., “Distance graph on $Z_n$ with $l_1$-norm”, Theoret. Comput. Sci., 319, Special issue on Combinatorics of the Discrete Plane and Tilings (2004), 357–366 | DOI | MR

[12] Z. Fiuredi, Kang, J-H., “Covering $n$-space by convex bodies and its chromatic number”, Disc. Math., 308, Special issue in honor of M. Simonovits (2008), 4495–4500 | DOI | MR

[13] Gardner, M., “The celebrated four-color map problem of topology”, Sci. Amer., 203 (1960), 218–226 | DOI | MR

[14] Gutman, I., “Selected properties of the Schultz molecular topological index”, J. Chem. Inf. Comput. Sci., 34 (1994), 1087–1089 | DOI

[15] Gutman, I, Cyvin, S. J., Introduction to the Theory of Benzenoid Hydrocarbons, Springer-Verlag, Berlin, 1989

[16] Hadwiger, H and Debrunner, H., Combinatorial Geometry in the plane, Holt, Rinehart and Winston, New York, 1964 | MR

[17] Johnson, P. D., “Coloring abelian groups”, Discrete Math., 40:2–3 (1982), 219–223 | DOI | MR | Zbl

[18] Kang, J-H and Maharaj, H., “Distance Graphs from $p$-adic Norms”, Integers, 10 (2010), 379–392 | DOI | MR | Zbl

[19] Khadikar, P. V., Deshpande, N. V., Kale, P. P., Dobrynin, A., Gutman, I., Domotor, G., “The Szeged index and some of its analogies with the Wiener index”, J. Chem. Inf. Comput. Sci., 35 (1995), 547–550 | DOI

[20] Kiran B. Chilakamarri, “Unit-distance graphs in rational $n$-spaces”, Discrete Math., 69:3 (1988), 213–218 | DOI | MR | Zbl

[21] Kiran B. Chilakamarri, “On the chromatic number of rational five-space”, Aequationes Math., 39:2–3 (1990), 146–148 | MR | Zbl

[22] Kiran B. Chilakamarri, “The unit-distance graph problem: a brief survey and some new results”, Bull. Inst. Combin. Appl., 8 (1993), 39–60 | MR | Zbl

[23] Klaviar, S., Gutman, I. and Mohar, B., “Labeling of Benzenoid Systems which Reflects the Vertex-Distance Relations”, J. Chem. Inf. Comput. Sci., 35 (1995), 590–593 | DOI

[24] Klein, D. J., Mihalic. Z., PlavSic. D., Trinajstic, N., “Molecular topological index. A relation with the Wiener index”, J. Chem. Inf. Comput. Sci., 32 (1992), 304–305 | DOI

[25] Knop, J. V., Muller, W. R., Szymanski K., Trinajstic N., “On the determinant of the adjacency-plus-distance matrix as a topological index for characterizing alkanes”, J. Chem. Inf. Comput. Sci., 31 (1991), 83–84 | DOI

[26] Larman, D. G., Rogers, C. A., “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[27] Mihalic, Z., Nikolic, S., Trinajstic, N., “Comparative studies of the descriptors derived from the distance matrix”, J. Chem. Inf Comput. Sci., 32 (1992), 28–37 | DOI

[28] Mihalic, Z, Trinajstic, N., “A graph-theoretical approach to structureproperty relationships”, J. Chem. Educ., 69 (1992), 701–712 | DOI

[29] Mihalic, Z., Veljan, D., Amic, D., Nikolic, S., PlavSic, D., Trinajstic, N., “The distance matrix in chemistry”, J. Math. Chem., 11 (1992), 223–258 | DOI

[30] Mordell, L. J., Diophantine Equations, Academic Press, London, 1969 | MR | Zbl

[31] Muller, W. R, Szymanski. K, Knop. J. V, Trinajstic, N., “Molecular topological index”, J. Chem. Inf. Comput. Sci., 30 (1990), 160–163 | DOI

[32] Plavsic, D., Nikolic, S., Trinajstic, N., Mihalic, Z., “On the Harary index for the characterization of chemical graphs”, J. Math. Chem., 12 (1993), 235–250 | DOI | MR

[33] Rado, R., “Axiomatic treatment of rank in infinite sets”, Canad. J. Math., 1 (1949), 337–343 | DOI | MR | Zbl

[34] Randic, M., “Novel molecular descriptor for structure-property studies”, Chern. Phys. Lett., 211 (1993), 478–483 | DOI

[35] Randic, M., Guo, X., Oxley, T., Krishnapriyan, H., “Wiener matrix: Source of novel graph invariants”, J. Chem. Inf. Comput. Sci., 1993

[36] Randic, M, Guo, X, Oxley, T, Krishnapriyan, H, Naylor, L., “Wiener matrix invariants”, J. Chem. Inf. Compul. Sci., 34 (1994), 361–367 | DOI

[37] Raigorodskii, A. M., “On the chromatic number of a space”, Russ. Math. Surveys, 55 (2000), 351–352 | DOI | MR | Zbl

[38] Raigorodskii, A. M., “Borsukâs problem and the chromatic numbers of some metric spaces”, Russ. Math. Surveys, 56 (2001), 103–139 | DOI | MR | Zbl

[39] Raigorodskii, A. M., “The Erdös-Hadwiger problem, and the chromatic number of finite geometric graphs”, Doklady Russian Acad. Sci., 392 (2003), 313–317 | MR | Zbl

[40] Raigorodskii, A. M., “On the chromatic number of a space with $q$-norm”, Russ. Math. Surveys, 59 (2004), 973–975 | DOI | MR | Zbl

[41] Ruzsa, I. Z., Tuza, Zs., Voigt, M., “Distance graphs with finite chromatic number”, J. Combin. Theory Ser. B, 85:1 (2002), 181–187 | DOI | MR | Zbl

[42] Sachs, H., “Perfect matchings in hexagonal systems”, Combinatorica, 4 (1984), 89–99 | DOI | MR | Zbl

[43] Schultz, H. P., “Topological organic chemistry. 1. Graph theory and topological indices of alkanes”, J. Chem. Inf. Cumput. Sci., 29 (1989), 227–228 | DOI

[44] Schultz, H. P., Schultz, E. B, Schultz, T. P., “Topological organic chemistry. 2. Graph theory, matrix determinants and eigenvalues and topological indices of alkanes”, J. Chem. Inf. Comput. Sci., 30 (1990), 27–29 | DOI

[45] Schultz, H. P., Schultz, T. P., “Topological organic chemistry. 3. Graph theory, binary and decimal adjacency matrices, and topological indices of alkanes”, J. Chem. Inf. Comput. Sci., 31 (1991), 144–147 | DOI

[46] Schultz, H. P., Schultz, E. B., Schultz, T. P., “Topological organic chemistry. 4. Graph theory. matrix permanents and topological indices of alkanes”, J. Chem. In Comput. Sci., 32 (1992), 69–72 | DOI

[47] Schultz, H. P., Schultz, T. P., “Topological organic chemistry. 5. Graph theory, matrix Hafnians and Pfaffians, and topological indices of alkanes”, J. Chem. In Comput. Sci., 32 (1992), 364–366 | DOI

[48] Soifer, A., “Chromatic number of the plane its relatives I. The problem its history”, Geombinatorics, 12:3 (2003), 131–148 | MR | Zbl

[49] Soifer, A. and Shelah, S., “Axiom of choice and chromatic number of the plane”, J. Combin.Theory Ser. A, 103:2 (2003), 387–391 | DOI | MR | Zbl

[50] Soifer, A. and Shelah, S., “Axiom of choice and chromatic number: examples on the plane”, J. Combin. Theory Ser. A, 105:2 (2004), 359–364 | DOI | MR | Zbl

[51] Trinajstic, N., Chemical Graph Theon, 2nd revised ed., CRC Press, Boca Raton, FL, 1992 | MR

[52] Wiener, H., “Structural determination of paraffin boiling points”, J. Am. Chem. Soc., 69 (1947), 17–20 | DOI

[53] Voigt, M., “On the chromatic number of distance graphs”, J. Inform. l Process. Cybernet. EIK, 28 (1992), 21–28 | Zbl

[54] Voigt, M., Die chromatische Zahl einer Speziellen Klasse unendlicher Graphen, Dissertations Schrift, Techn. Univ. Hemanau, 1992

[55] Von Mag. Ingrid G. Abfalter, Nucleic Acid Sequence Design as a Graph Coloring Problem, Dissertation zur Erlangung des akademischen Grades Doktor rerum naturalium, Vorgelegt der Fakultat fur chemie der Universitat Wien, am Institut fur Theoretische Chemie und Molekulare Struktur Biologie, Nov, 2005

[56] Woodall, D. R., “Distances realized by sets covering the plane”, J. Combinatorial Theory Ser. A, 14 (1973), 187–200 | DOI | MR | Zbl

[57] Woodall, D. R., “Distances realized by sets covering the plane”, J. Combinatorial Theory Ser. A, 14 (1973), 187–200 | DOI | MR | Zbl

[58] Zhu, X., “Pattern periodic coloring of distance graphs”, J. Combin. Theory B, 73 (1998), 195–206 | DOI | MR | Zbl

[59] Zhu, X., Diophantine approximations and coloring of distance graphs, Manuscript, 1998