Largest reduced neighborhood clique cover number revisited

Abstract

Let $G$ be a graph and $t\ge 0$. The largest reduced neighborhood clique cover number of $G$, denoted by ${\hat{\beta }}_t(G)$, is the largest, overall $t$-shallow minors $H$ of $G$, of the smallest number of cliques that can cover any closed neighborhood of a vertex in $H$. It is known that ${\hat{\beta }}_t(G)\le s_t$, where $G$ is an incomparability graph and $s_t$ is the number of leaves in a largest $t-$shallow minor which is isomorphic to an induced star on $s_t$ leaves. In this paper we give an overview of the properties of ${\hat{\beta }}_t(G)$ including the connections to the greatest reduced average density of $G$, or ${▽}_t(G)$, introduce the class of graphs with bounded neighborhood clique cover number, and derive a simple lower and an upper bound for this important graph parameter. We announce two conjectures, one for the value of ${\hat{\beta }}_t(G)$, and another for a separator theorem (with respect to a certain measure) for an interesting class of graphs, namely the class of incomparability graphs which we suspect to have a polynomial bounded neighborhood clique cover number, when the size of a largest induced star is bounded.

The results in this paper were presented in 48th Southeastern Conference in Combinatorics, Graph Theory and Computing, Florida Atlantic University, Boca Raton, March 2017

References in corpus (5)

• Characterisations and Examples of Graph Classes with Bounded Expansion
• A new separation theorem with geometric applications
• Constant-factor approximation of domination number in sparse graphs
• On the largest reduced neighborhood clique cover number of a graph
• Unit Incomparability Dimension and Clique Cover Width in Graphs