The conjecture that every critical graph is 1-unique

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.