On the largest reduced neighborhood clique cover number of a graph

Abstract

Let $G$ be a graph and $t\ge 0$. A new graph parameter termed the largest reduced neighborhood clique cover number of $G$, denoted by ${\hat{\beta }}_t(G)$, is introduced. Specifically, ${\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$. We verify that ${\hat{\beta }}_t(G)=1$ when $G$ is chordal, and, ${\hat{\beta }}_t(G)\le s$, where $G$ is an incomparability graph that does not have a $t-$shallow minor which is isomorphic to an induced star on $s$ leaves. Moreover, general properties of ${\hat{\beta }}_t(G)$ including the connections to the greatest reduced average density of $G$, or ${▽}_t(G)$ are studied and investigated. For instance we show $\frac{{\hat{\beta }}_t(G)}{2}\le {▽}_t(G)\le p.{\hat{\beta }}_t(G),$ where $p$ is the size of a largest complete graph which is a $t-minor$ of $G$. Additionally we prove that largest ratio of any minimum clique cover to the maximum independent set taken overall $t-$minors of $G$ is a lower bound for ${\hat{\beta }}_t(G)$. We further introduce the class of bounded neighborhood clique cover number for which ${\hat{\beta }}_t(G)$ has a finite value for each $t\ge 0$ and verify the membership of geometric intersection graphs of fat objects (with no restrictions on the depth) to this class. The results support the conjecture that the class graphs with polynomial bounded neighborhood clique cover number may have separator theorems with respect to certain measures.

A portion of these results were presented at the 47th Southeast Conference on Combinatorics, Graph Theory and Computing, March 7-11, 2016 and will appear in the conference proceedings, Congressus Numerantium (2016)

References in corpus (4)

• 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
• New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects

Cited by in corpus (1)

• Largest reduced neighborhood clique cover number revisited