Пусть класс графов с ограниченной шириной клика. В каждом графе в некоторые ребра сжимаются (например, случайно). Теперь ширина клики все еще ограничена?
Если это (вообще) больше не ограничено, я был бы очень заинтересован в контрпримере.
graph-theory
co.combinatorics
cliquewidth
Мартин Лакнер
источник
источник
Эта недавняя статья в конечном итоге доказывает, что сужения ребер не сохраняют свойство ограниченности ширины клика для набора графов.
источник