Раскраски планарных графиков

21

Рассмотрим множество плоских графов, где все внутренние грани являются треугольниками. Если есть внутренняя точка нечетной степени, график не может быть трехцветным. Если каждая внутренняя точка имеет четную степень, она всегда может быть трехцветной? В идеале я хотел бы небольшой контрпример.

graph-theory co.combinatorics graph-colouring Лэнс Фортноу
источник

Ответы:

25

Да, это является следствием теоремы о трех цветах, см. Здесь внизу: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
источник
1
Спасибо. У вас есть ссылка для доказательства?
Ланс Фортноу
3
Вы можете посмотреть на эти две статьи: google.com/… и google.com/…
Джозеф Малкевич
6
Чтобы добавить к ссылкам Малкевича: эквивалентность 3-окрашиваемости и даже степени для плоских триангуляций обычно приписывают П. Дж. Хивуду "О теореме о четырехцветном отображении". Ежеквартально J. Pure Appl. Математика 29: 270–285, 1898. Однако в работах, связанных с Малкевичем, есть еще что сказать об этой атрибуции.
Дэвид Эппштейн
6
Кроме того, следствие не упоминается в заметках Халла, только сама теорема о 3 цветах. Но из 3-связного графа G с треугольными внутренними гранями и даже внутренними вершинами можно сформировать максимальный планарный граф 2G с четными вершинами, просто сшив две копии G на внешней грани. Если G не является 3-связным, можно независимо раскрасить его 3-компонентные компоненты в 3 цвета.
Дэвид Эппштейн