Let be a graph and . The largest reduced neighborhood clique cover number of , denoted by , is the largest, overall -shallow minors of , of the smallest number of cliques that can cover any closed neighborhood of a vertex in . It is known that , where is an incomparability graph and is the number of leaves in a largest shallow minor which is isomorphic to an induced star on leaves. In this paper we give an overview of the properties of including the connections to the greatest reduced average density of , or , 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 , 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本