On chromatic number of unit-quadrance graphs (finite Euclidean graphs)
| dc.creator | Vinh, Le Anh | |
| dc.date | 2005-10-05 | |
| dc.date.accessioned | 2026-07-07T06:21:09Z | |
| dc.date.available | 2026-07-07T06:21:09Z | |
| dc.description | The quadrance between two points A_1=(x_1, y_1) and A_2=(x_2, y_2) is the number Q (A_1, A_2) = (x_1 - x_2)^2 + (y_1 - y_2)^2. Let q be an odd prime power and F_q be the finite field with $q$ elements. The unit-quadrance graph D_q has the vertex set F_q^2, and X, Y in F_q^2 are adjacent if and only if Q(A_1, A_2) = 1. Let χ(F_q^2) be the chromatic number of graph D_q. In this note, we will show that q^{1/2}(1/2+o(1)) <= χ(F_q^2) <= q(1/2 + o(1)). As a corollary, we have a construction of triangle-free graphs D_q of order q^2 with χ(D_q) >= q/2 for infinitely many values of q. | |
| dc.description | 5 pages | |
| dc.identifier | https://arxiv.org/abs/math/0510092 | |
| dc.identifier | http://arxiv.org/abs/math/0510092 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/95508 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | On chromatic number of unit-quadrance graphs (finite Euclidean graphs) | |
| dc.type | text |