We study simultaneous color densities in packing colorings of integer distance graphs. For $D(1,6)$, we determine several exact density regions and prove that colors $1$ through $7$ have maximum combined density $211/252$. When this maximum is approached, the seven individual color frequencies are forced to converge to a specified vector. On an optimal low-color layer, some density vectors have nonperiodic realizations but no periodic realization; we determine how much accumulated density loss is necessary for switching between the relevant configurations. For sufficiently large additional color indices, a fixed finite graph describes the joint density region. In particular, we determine a seven-vertex region for every $i\equiv8\pmod{14}$ with $i\ge36$ and prove that $36$ is the first stable index in this residue class. The proofs combine finite-state integer certificates with explicit constructions and limit arguments. Applications give $17\le\chi_\rho(D(1,6))\le20$, $18\le\chi_\rho(D(1,8))\le22$, and $\chi_\rho(D(1,9))\le17$.
We show that almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts. Equivalently, for $G\sim G(n,1/2)$, $\chi_m(G)\le3$ with high probability, improving the previously known bound of five. Here $\chi_m(G)$...
Let $\mathcal P_1$ denote the class of 1-planar graphs and let $tC_5$ be the disjoint union of $t$ copies of $C_5$. For every fixed $t\ge3$ and all sufficiently large $n$, we determine the unique $n$-vertex $tC_5$-free graph in $\mathcal P_1$ with maximum adjacency spectral radius, answering Problem 1 of Li, Wang and Z...
Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing and an analytic minimization argument of Alon, Buci\'c, and Davies. For every integer $q\ge2$, we prove that $q$ edge-disjoint spanning trees suffice to realize every co...
Let $G$ be a simple graph with maximum degree $\Delta\ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\ell}(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\ell}(G,k)=P(G,k)$ for every...
Let $\tau(G)$ denote the maximum number of edge-disjoint spanning trees in a connected graph $G$ of order $n$, and let $\rho_D(G)$ denote its distance spectral radius. For an integer $k\ge2$, Fan, He and Zhao [Discrete Appl. Math. 376 (2025) 31--40] obtained a sharp distance spectral radius condition for $\tau(G)\ge k$...
We study the largest size $C(n)$ of a subset of the $n\times n$ integer grid containing no isosceles triple, including equally spaced collinear triples. We prove $C(n)=\Omega\left(n\sqrt{\log\log n/\log n}\right)$ by applying the sparse hypergraph coloring theorem of Cooper and Mubayi. Elementary geometry and primitive...
Yu-Kai Song· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
