The incomparability-graph shallow-minor star conjecture
The incomparability-graph shallow-minor star conjecture
Let be an incomparability graph, and let be the number of leaves in a largest induced star in . A -shallow minor is a graph obtained from pairwise vertex-disjoint subgraphs of radius at most by contracting each subgraph to one vertex. Let denote the number of leaves in a largest induced star in a -shallow minor of , and let denote the reduced neighborhood clique cover number at depth .
Shallow-minor star conjecture. If does not have an induced star on leaves, then, for every ,
Consequently,
If true, this would give a linear bound on the neighborhood clique cover number for incomparability graphs when the largest induced-star size is fixed. The source does not provide a resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Farhad Shahrokhi, “Largest reduced neighborhood clique cover number revisited”, arXiv:1705.02537 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.