The incomparability-graph shallow-minor star conjecture

Let GG be an incomparability graph, and let ss be the number of leaves in a largest induced star in GG. A tt-shallow minor is a graph obtained from pairwise vertex-disjoint subgraphs of radius at most tt by contracting each subgraph to one vertex. Let sts_t denote the number of leaves in a largest induced star in a tt-shallow minor of GG, and let β^t(G){\hat\beta}_t(G) denote the reduced neighborhood clique cover number at depth tt.

Shallow-minor star conjecture. If GG does not have an induced star on ss leaves, then, for every t0t\ge 0,

st=O(t.s).s_t=O(t.s).

Consequently,

β^t(G)=O(t.s).{\hat\beta}_t(G)=O(t.s).

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

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.