The tree cover bound for connected triangle-free graphs

About 8 years old · traced to

Let GG be a connected triangle-free graph on nn vertices, and let T(G)T(G) denote its tree cover number.

Triangle-free tree cover conjecture. For all connected triangle-free graphs,

T(G)≤⌈n3⌉.T(G)\leq\left\lceil\frac{n}{3}\right\rceil.

The question arises because a related bound for graphs of girth at least five does not extend to the four-cycle; the conjecture is motivated by computations in Sage and remains open in the supplied source.

References

Primary source

Chassidy Bozeman, “On the tree cover number and the positive semidefinite maximum nullity of a graph”, arXiv:1810.09728 (2020).

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.