Сохраняется ли ширина клики при сжатии краев?

13

Пусть класс графов с ограниченной шириной клика. В каждом графе в некоторые ребра сжимаются (например, случайно). Теперь ширина клики все еще ограничена?GG

Если это (вообще) больше не ограничено, я был бы очень заинтересован в контрпримере.

Мартин Лакнер
источник

Ответы:

16

Это может быть предварительным ответом: в данной статье arXiv 2007 года (проблема 4.9) в качестве открытой проблемы указывается, можно ли найти граф G и ребро {x,y}E(G) такое что cw(G)<cw(Gx,y) , где Gx,y - граф G с ребром {x,y} .

Матье Шапель
источник
Большое спасибо за ваш ответ! Это ценная ссылка для меня. Если пока что никто не решил, на мой вопрос более или менее ответили :)
Martin Lackner
Разве эта проблема не противоположна тому, что здесь задают?
Цуёси Ито
Только в том смысле, что этот вопрос требует контрпример.
Мартин Лакнер,
17

Эта недавняя статья в конечном итоге доказывает, что сужения ребер не сохраняют свойство ограниченности ширины клика для набора графов.

user13136
источник