The conjecture that every critical graph is 1-unique

About 9 years old · traced to

A graph GG is 1-unique if, for every vertex vv of GG, there is a tree-depth labeling using labels from {1,…,td⁡(G)}\{1,\dots,\operatorname{td}(G)\} in which vv is the unique vertex receiving label 11. A graph is critical when it is kk-critical for its tree-depth kk: every proper minor has smaller tree-depth.

Every-critical-graph conjecture. Every critical graph is 1-unique.

The conjecture is motivated by the fact that every critical graph with tree-depth at most 44 is 1-unique, and that critical graphs produced by certain known constructions are also 1-unique. Its status is not resolved by the supplied text.

References

Primary source

Michael D. Barrus and John Sinkovic, “On 1-uniqueness and dense critical graphs for tree-depth”, arXiv:1704.07311 (2017).

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.