The planar bichromatic graph algebraic-connectivity conjecture

Let GG be a planar bichromatic graph, meaning a planar graph whose vertices can be coloured with two colours so that adjacent vertices have different colours. Let a(G)a(G) denote its algebraic connectivity. Bichromatic planar algebraic-connectivity conjecture.

a(G)2.a(G)\leq 2.

The preceding discussion gives the weaker bound a(G)3a(G)\leq 3; this conjecture proposes that the bound can be improved to two.

Sources & referencesView supporting material

Primary source

Pedro Freitas, “A Heawood-type result for the algebraic connectivity of graphs on surfaces”, arXiv:math/0109191 (2001).

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.