Клик-ширина почти Cographs

(Я отправил этот вопрос в MathOverflow две недели назад, но пока без точного ответа)

У меня есть вопрос о мерах ширины графа неориентированных простых графов. Хорошо известно, что cographs (графы, которые могут быть построены операциями дизъюнктного объединения и дополнения, начиная с изолированных вершин), имеют ширину кликов не более 2. (Courcelle et al. Верхние границы ширины кликов графов). Теперь рассмотрим некоторое фиксированное неотрицательное целое число k и рассмотрим класс графов такой, что для каждого существует множество из большинство k вершин такие, что является рефератом. Поскольку класс графов также можно рассматривать как класс графов, который можно построить из графов, добавив не более$\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$$\mathcal{G} _k$$k$вершины, этот класс также называется Cographs + .$kv$

Мой вопрос: что является жесткой границей ширины кликов в , т. Е. Графов, которые можно превратить в cograph, удалив k вершин?$\mathcal{G}_k$

Известно, что если граф получается из удалением вершин, то . Это показывает, что если из графа можно получить cограф , удалив вершин, то и, следовательно, ширина клика графа в равна максимум . Я не уверен, нужна ли эта экспоненциальная зависимость от . В этом контексте я также был бы заинтересован в максимальном уменьшении ширины клики путем удаления вершины; т.е. если мы удалим одну вершину из графа, насколько может уменьшиться ширина клика?$G$$H$$k$$cw(H) \leq 2^k (cw(G) + 1)$$G$$H$$k$$cw(H) \leq 2^k (3 + 1)$$\mathcal{G}_k$$4*2^k$$k$

Я постараюсь ответить на этот ваш старый вопрос, хотя я не уверен, что мой ответ является окончательным, но он должен указать вам правильное направление.

Сначала давайте обсудим линейную ширину клики. Если граф имеет линейную кликовую ширину , и к нему добавляется вершина, эта вершина всегда может быть помещена первой в порядке с уникальным цветом. Следовательно, линейная ширина клика увеличивается не более чем на 1 при добавлении вершины.$k$$1$

Гурски и Ванке показали в «О связи между шириной NLC и линейной шириной NLC», что у cographs есть неограниченная линейная ширина клики.

Так как у cographs есть неограниченная линейная ширина клики, но ограниченная ширина клики, любое хорошее разложение клики должно иметь древовидную структуру. Мы должны показать, что мы можем вызвать произвольно много глубоких ветвей. Теперь мы делаем то же самое, что и для деревьев, строим дерево с 2 ^ k листьями, добавляем k вершин, и каждый лист связан с уникальным подмножеством новых вершин.