Maxmaxflow conjecture for bounded chromatic roots

About 26 years old · traced to

For a graph GG, define the edge-connectivity between distinct vertices xx and yy by

λ(x,y)=the maximum number of edge-disjoint paths from x to y=the minimum number of edges separating x from y,\lambda(x,y)=\text{the maximum number of edge-disjoint paths from $x$ to $y$}=\text{the minimum number of edges separating $x$ from $y$},

and define the maxmaxflow by

Λ(G)=max⁡x≠yλ(x,y).\Lambda(G)=\max_{x\neq y}\lambda(x,y).

Maxmaxflow conjecture. There exist universal constants C(k)<∞C(k)<\infty such that every chromatic root zz of any graph GG with Λ(G)=k\Lambda(G)=k lies in the disc

∣z−1∣≤C(k).|z-1|\leq C(k).

This weakens a bound in terms of the second-largest vertex degree. The paper notes that linear growth of C(k)C(k) in kk is natural to expect, but does not prove the conjecture for arbitrary graphs.

References

Primary source

Jason Brown, Carl Hickman, Alan D. Sokal and David G. Wagner, “On the chromatic roots of generalized theta graphs”, arXiv:math/0012033 (2000).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.