Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911141519687680 |
|---|---|
| author | Lopez-Bonilla, Rogelio N. Allagan, Julian Langley, Shawn M. Clinton, Angel J. |
| author_facet | Lopez-Bonilla, Rogelio N. Allagan, Julian Langley, Shawn M. Clinton, Angel J. |
| contents | We study generalized circular chord graphs $\mathcal C^{(k)}_n$, formed from a cycle $C_n$ by adding fixed-offset chords of length $k$ and, for even $n$, diameters. Using transfer matrix methods, we derive exact formulas for 3-colorings when $k=3$: for odd $n$, we obtain \[ P(\mathcal{C}_n^{(3)},3) = L_n + 2\cos\left(\frac{2πn}{3}\right) + 2s_n + 2 \] where $L_n$ is the Lucas sequence and $(s_n)$ satisfies $s_{n+3} = -s_{n+2} - s_n$, yielding golden-ratio asymptotic growth $φ^n + O(ρ^n)$ along odd indices. For even $n$, we construct a paired-window transfer matrix that exactly enumerates $P(\mathcal{C}_{2m}^{(3)},3)$ while capturing diameter constraints. The chromatic counts exhibit pronounced modular patterns across residue classes without universal vanishing rules (see OEIS A383733). We provide efficient algorithms for exact enumeration and demonstrate applications to cyclic scheduling problems where these results serve as feasibility engines for airline gate assignment, wireless sensor networks, and multiprocessor task coordination. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05845 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs Lopez-Bonilla, Rogelio N. Allagan, Julian Langley, Shawn M. Clinton, Angel J. Combinatorics Discrete Mathematics 68R10, 05C85 G.2.1; G.2.2; G.2.3; I.1.2 We study generalized circular chord graphs $\mathcal C^{(k)}_n$, formed from a cycle $C_n$ by adding fixed-offset chords of length $k$ and, for even $n$, diameters. Using transfer matrix methods, we derive exact formulas for 3-colorings when $k=3$: for odd $n$, we obtain \[ P(\mathcal{C}_n^{(3)},3) = L_n + 2\cos\left(\frac{2πn}{3}\right) + 2s_n + 2 \] where $L_n$ is the Lucas sequence and $(s_n)$ satisfies $s_{n+3} = -s_{n+2} - s_n$, yielding golden-ratio asymptotic growth $φ^n + O(ρ^n)$ along odd indices. For even $n$, we construct a paired-window transfer matrix that exactly enumerates $P(\mathcal{C}_{2m}^{(3)},3)$ while capturing diameter constraints. The chromatic counts exhibit pronounced modular patterns across residue classes without universal vanishing rules (see OEIS A383733). We provide efficient algorithms for exact enumeration and demonstrate applications to cyclic scheduling problems where these results serve as feasibility engines for airline gate assignment, wireless sensor networks, and multiprocessor task coordination. |
| title | Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs |
| topic | Combinatorics Discrete Mathematics 68R10, 05C85 G.2.1; G.2.2; G.2.3; I.1.2 |
| url | https://arxiv.org/abs/2509.05845 |