← Back to Theme 4: Distribution of zeroes in the complex plane
Let \(G\) be a loopless graph and \[\Lambda=\min_\mathcal{B}\{\max_{C\in \mathcal{B}}\{|C|\}\}\] where the minimum is taken over all bases \(\mathcal{B}\) of the cocycle space of \(G\).
Conjecture: There exists a constant \(c\) such that all complex roots of the chromatic polynomial \(P_G(q)\) of \(G\) lie in a disc \(|q|\leq c\Lambda\).
Let \(G\) be a bridgeless graph and \[\Lambda^*=\min_\mathcal{B}\{\max_{C\in \mathcal{B}}\{|C|\}\}\] where the minimum is taken over all bases \(\mathcal{B}\) of the cycle space of \(G\).
Conjecture: Then there exist universal constants \(c_{\Lambda^*}\) such that all complex roots of the flow polynomial \(F_G(q)\) of \(G\) lie in a disc \(|q|\leq c_{\Lambda^*}\).
Let \(M\) be a loopless binary matroid and \[\Lambda=\min_\mathcal{B}\{\max_{C\in \mathcal{B}}\{|C|\}\}\] where the minimum is taken over all bases \(\mathcal{B}\) of the cocycle space of \(M\).
Conjecture: Then there exists universal constants \(c_{\Lambda}\) such that all complex roots of the characteristic polynomial \(C_M(q)\) of \(M\) lie in a disc \(|q|\leq c_{\Lambda}\).
Some evidence in support of conjectures P4.1.1, P4.1.2, P4.1.3 can be found in [Jackson--Sokal (2010), Conjecture 1.1], [Jackson (2013)], [Royle--Sokal (2015)].
We thank Bill Jackson for sharing these conjectures.
Let \(G\) be a bipartite planar graph and let \(P_G(q)\) be its chromatic polynomial.
Conjecture: Then \(P_G(q)>0\) for all real \(q\ge 3\).
Let \(G\) be a plane quadrangulation and let \(P_G(q)\) be its chromatic polynomial.
Conjecture: Then \(P_G(q)>0\) for all real \(q\ge 3\).
Let \(G\) be a bridgeless graph and let \(\Phi_G(q)\) be its flow polynomial.
Conjecture: Then \(\Phi_G(q)>0\) for all real \(q\ge 6\).
We thank Jesus Salas for sharing conjectures P4.1.4, P4.1.5, P4.1.6, P4.1.7.
Conjecture P4.1.6 is a translation of the Birkoff--Lewis theorem, in the same way as Tutte's 5-flow conjecture is the translated version of the 4-color theorem.
For the next conjecture, the graph \(S_{m,n}\) is the square grid with \(m\times n\) vertices such that all its leftmost vertices are connected to an additional vertex to the left and all its rightmost vertices are connected to an additional vertex to the right; see [Salas--Sokal (2011), Figure 1a].
Conjecture: There exists a constant \(Q<\infty\) such that the chromatic roots of the graphs \(S_{m,n}\) become dense in the region \(|q|>Q\) when \(m,n\to\infty\).
(P4.1.8) Conjecture: For \(r\ge 4\) the complete bipartite graph \(K_{r,r}\) is the graph of maximum degree \(r\) having the largest chromatic roots (in modulus).
(P4.1.8') Conjecture: For \(r\ge 3\) the complete bipartite graph \(K_{r,r}\) is the graph of maximum degree \(r\) having the largest chromatic roots (in modulus) (excluding \(K_4\) when \(r=3\)).
Let \(G\) be a loopless graph and let \(\Delta\) denote its maximum degree.
Conjecture: All the chromatic roots (real or complex) of all loopless graphs of maximum degree \(\Delta\) lie in the half-plane \({\rm Re }\; q \le \Delta\).
Conjecture: Are the chromatic roots of planar graphs dense in the complex plane?
We thank Guus Regts for sharing conjectures P4.1.8, P4.1.9, P4.1.10.