×

Fractional chromatic number of distance graphs generated by two-interval sets. (English) Zbl 1246.05058

Summary: Let \(D\) be a set of positive integers. The distance graph generated by \(D\), denoted by \(G(Z,D)\), has the set \(Z\) of all integers as the vertex set, and two vertices \(x\) and \(y\) are adjacent whenever \(|x - y|\in D\). For integers \(1<a\leq b<m - 1\), define \(D_{a,b,m}=\{1,2,\ldots ,a - 1\}\cup \{b+1,b+2,\ldots ,m - 1\}\). For the special case \(a=b\), the chromatic number for the family of distance graphs \(G(Z,D_{a,a,m})\) was first studied by R. B. Eggleton, P. Erdős and D. K. Skilton [“Colouring the real line,” J. Comb. Theory, Ser. B 39, 86–100 (1985); Errata ibid. 41, 139 (1986; Zbl 0549.05029)] and was completely solved by G. Chang, D. Liu and X. Zhu [“Distance graphs and \(T\)-coloring,” J. Comb. Theory, Ser. B 75, No. 2, 259–269 (1999; Zbl 0930.05037)].
For the general case \(a\leq b\), the fractional chromatic number for \(G(Z,D_{a,b,m})\) was studied by P. C. B. Lam and W. Lin [“Coloring distance graphs with intervals as distance sets,” Eur. J. Comb. 26, No. 8, 1216–1229 (2005; Zbl 1082.05038)] and by J. Wu and W. Lin [“Circular chromatic numbers and fractional chromatic numbers of distance graphs with distance sets missing an interval,” Ars Comb. 70, 161–168 (2004; Zbl 1093.05026)], in which partial results for special values of \(a,b,m\) were obtained. In this article, we completely settle this problem for all possible values of \(a,b,m\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cantor, D. G.; Gordon, B., Sequences of integers with missing differences, J. Combin. Theory (A), 14, 281-287 (1973) · Zbl 0277.10043
[2] Chang, G. J.; Huang, L.; Zhu, X., The circular chromatic numbers and the fractional chromatic numbers of distance graphs, European J. Combin., 19, 423-431 (1998) · Zbl 0905.05032
[3] Chang, G.; Liu, D.; Zhu, X., Distance graphs and \(T\)-coloring, J. Combin. Theory (B), 75, 159-169 (1999)
[4] Chen, J.; Chang, G. J.; Huang, K., Integral distance graphs, J. Graph Theory, 25, 287-294 (1997) · Zbl 0878.05028
[5] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring the real line, J. Combin. Theory (B), 39, 86-100 (1985) · Zbl 0549.05029
[6] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Research problem 77, Discrete Math., 58, 323 (1986)
[7] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Update information on research problem 77, Discrete Math., 69, 105 (1988)
[8] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring prime distance graphs, Graphs Combin., 6, 17-32 (1990) · Zbl 0698.05033
[9] Griggs, J.; Liu, D., The channel assignment problem for mutually adjacent sites, J. Combin. Theory (A), 68, 169-183 (1994) · Zbl 0816.05027
[10] Haralambis, N. M., Sets of integers with missing differences, J. Combin. Theory (A), 23, 22-33 (1977) · Zbl 0359.10047
[11] Kemnitz, A.; Kolberg, H., Coloring of integer distance graphs, Discrete Math., 191, 113-123 (1998) · Zbl 0956.05044
[12] Kemnitz, A.; Marangio, M., Colorings and list colorings of integer distance graphs, Congr. Numer., 151, 75-84 (2001) · Zbl 0989.05039
[13] Kemnitz, A.; Marangio, M., Chromatic numbers of integer distance graphs, Discrete Math., 233, 239-246 (2001) · Zbl 0988.05039
[14] Lam, P.; Lin, W., Coloring distance graphs with intervals as distance sets, European J. Combin., 26, 1216-1229 (2005) · Zbl 1082.05038
[15] Lin, W.; Lam, P.; Song, Z., Circular chromatic numbers of some distance graphs, Discrete Math., 292, 119-130 (2005) · Zbl 1063.05045
[16] Liu, D., \(T\)-coloring and chromatic number of distance graphs, Ars Combin., 56, 65-80 (2000) · Zbl 0994.05062
[17] Liu, D.; Zhu, X., Distance graphs with missing multiples in the distance sets, J. Graph Theory, 30, 245-259 (1999) · Zbl 0915.05056
[18] Liu, D.; Zhu, X., Fractional chromatic number and circular chromatic number for distance graphs with large clique size, J. Graph Theory, 47, 129-146 (2004) · Zbl 1055.05059
[19] Rabinowitz, J.; Proulx, V., An asymptotic approach to the channel assignment problem, SIAM J. Alg. Disc. Methods, 6, 507-518 (1985) · Zbl 0579.05058
[20] Voigt, M., Colouring of distance graphs, Ars Combin., 52, 3-12 (1999) · Zbl 0977.05047
[21] Voigt, M.; Walther, H., Chromatic number of prime distance graphs, Discrete Appl. Math., 51, 197-209 (1994) · Zbl 0808.05051
[22] Walther, H., Über eine spezielle Klasse unendlicher Graphen, (Wagner, K.; Bodendiek, R., Graphentheorie II, BI Wissenschaftsverlag (Hrsg.) (1990)), 268-295 · Zbl 0698.05002
[23] Wu, J.; Lin, W., Circular chromatic numbers and fractional chromatic numbers of distance graphs with distance sets missing an interval, Ars Combin., 70, 161-168 (2004) · Zbl 1093.05026
[24] Zhu, X., The circular chromatic number of distance graphs with distance sets of cardinality 3, J. Graph Theory, 41, 195-207 (2002) · Zbl 1012.05071
[25] Zhu, X., The circular chromatic number of a class of distance graphs, Discrete Math., 265, 1-3, 337-350 (2003) · Zbl 1021.05040
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.