2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Разбиение кубического графа на два остовных подграфа...
Сообщение27.02.2025, 23:26 
Аватара пользователя


27/10/23
11
... без изолированных вершин.

Другими словами, нужно доказать, что рёбра 3-регулярного графа можно покрасить в два цвета так, чтобы из каждой вершины выходили рёбра обоих цветов.

Пытался решить, подвешивая граф за вершину. Но тут не видно ничего. Ещё задал эту задачу ДипСику.

Сначала он сказал, что рёбра любого графа можно ориентировать так, чтобы входящая и исходящая степени любой вершины отличались не более, чем на 1. Тогда покрасим все входящие в 1 цвет, а исходящие во 2 цвет :P

Вторая его попытка была более интересной. Он сказал, что по теореме Петерсона кубический граф без мостов содержит совершенное парасочетание. Его красим в один цвет, а всё остальное в другой. А так как в кубических графах мостов не бывает, то задача решена.

Но оказалось, что в кубических графах всё же бывают мосты, и бывают кубические графы, в которых нет совершенного парасочетания :-(

 Профиль  
                  
 
 Re: Разбиение кубического графа на два остовных подграфа...
Сообщение27.02.2025, 23:47 
Заслуженный участник


07/08/23
1394
Это легко следует из теоремы Визинга (рёбра можно раскрасить в $4$ цвета так, что рёбра одного цвета не имеют общих концов).

 Профиль  
                  
 
 Re: Разбиение кубического графа на два остовных подграфа...
Сообщение01.03.2025, 14:15 
Аватара пользователя


27/10/23
11
Да, действительно. Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: andreiandrei


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group