Chromatic number of graphs with special distance sets, I
Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance g...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2014
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/152354 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862536624955457536 |
|---|---|
| author | Yegnanarayanan, V. |
| author_facet | Yegnanarayanan, V. |
| citation_txt | Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance graphs G(Z, D)whose distance set D is either 1) a set of (n + 1) positive integers for which the nth power of the last is the sum of the nth 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 Ulam 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.
|
| first_indexed | 2025-11-24T11:38:36Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-152354 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-11-24T11:38:36Z |
| publishDate | 2014 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Yegnanarayanan, V. 2019-06-10T11:10:25Z 2019-06-10T11:10:25Z 2014 Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. 1726-3255 2010 MSC:05C15. https://nasplib.isofts.kiev.ua/handle/123456789/152354 Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance graphs G(Z, D)whose distance set D is either 1) a set of (n + 1) positive integers for which the nth power of the last is the sum of the nth 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 Ulam 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. This research is carried out with the financial grant and support of National Board for Higher Mathematics, Government of India under the grant sanction no. 2/48(10)/2005/R&D-II/11192/dated 26,Nov,2010. The author also thanks A. Parthiban his Ph.D. student for useful discussions. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Chromatic number of graphs with special distance sets, I Article published earlier |
| spellingShingle | Chromatic number of graphs with special distance sets, I Yegnanarayanan, V. |
| title | Chromatic number of graphs with special distance sets, I |
| title_full | Chromatic number of graphs with special distance sets, I |
| title_fullStr | Chromatic number of graphs with special distance sets, I |
| title_full_unstemmed | Chromatic number of graphs with special distance sets, I |
| title_short | Chromatic number of graphs with special distance sets, I |
| title_sort | chromatic number of graphs with special distance sets, i |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/152354 |
| work_keys_str_mv | AT yegnanarayananv chromaticnumberofgraphswithspecialdistancesetsi |