The conjecture that every critical graph is 1-unique
The conjecture that every critical graph is 1-unique
A graph is 1-unique if, for every vertex of , there is a tree-depth labeling using labels from in which is the unique vertex receiving label . A graph is critical when it is -critical for its tree-depth : 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 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
Sign in to submit a solution.
No solutions have been posted yet.