2014 dxdy logo

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

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




 
 Полные графы с цетными рёбрами
Сообщение27.07.2013, 11:16 
Аватара пользователя
У полного графа с 6-ю вершинами и рёбрами 2-х цветов есть 2 одноцветных треугольника, которые могут иметь общую сторону или только вершину, а могут и не иметь и быть разных цветов.
У графа из 8-ми вершин с рёбрами 2-х цветов имеется 2 одноцветных треугольника, которые не имеют общей вершины.
У графа из 17 вершин с рёбрами 3-х цветов имеется одноцветный треугольник.
А есть ли общие оценки для числа сцепленных и нет одноцветных треугольников для полного графа с n вершинами и рёбрами k цветов?

 
 
 
 Re: Полные графы с цетными рёбрами
Сообщение27.07.2013, 18:58 
Для раскраски в 4 цвета уже непонятно, какое минимальное количество вершин должно быть в графе, чтобы обязательно нашелся одноцветный треугольник. Оценку написать можно.

 
 
 
 Re: Полные графы с цетными рёбрами
Сообщение29.07.2013, 09:22 
Аватара пользователя
Видимо, для этого графа оценка - 61 вершина? Или есть методы точнее?

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group