Grafik Planar Pewarnaan

21

Pertimbangkan seperangkat grafik planar di mana semua wajah internal adalah segitiga. Jika ada titik interior dengan derajat ganjil, grafik tidak boleh tiga berwarna. Jika setiap titik interior memiliki derajat genap, bisakah selalu tiga warna? Idealnya saya ingin contoh kecil.

graph-theory co.combinatorics graph-colouring Lance Fortnow
sumber

Jawaban:

25

Ya, ini adalah akibat wajar dari Teorema Tiga Warna, lihat di bagian bawah di sini: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
sumber
1
Terima kasih. Apakah Anda memiliki referensi untuk bukti?
Lance Fortnow
3
Anda mungkin melihat dua makalah ini: google.com/… dan google.com/...
Joseph Malkevitch
6
Untuk menambah referensi Malkevitch: kesetaraan 3-warna dan tingkat genap untuk triangulasi planar biasanya dikaitkan dengan PJ Heawood, "Pada teorema peta empat warna". Triwulan J. Aplikasi Murni. Matematika 29: 270–285, 1898. Namun makalah yang dihubungkan Malkevitch lebih banyak bicara tentang atribusi ini.
David Eppstein
6
Juga, akibat wajarnya tidak disebutkan dalam catatan Hull, hanya teorema 3-warna itu sendiri. Tetapi dari grafik 3-terhubung G dengan wajah internal segitiga dan bahkan simpul internal seseorang dapat membentuk grafik planar maksimal 2G dengan simpul genap hanya dengan menjahit dua salinan G pada permukaan luar. Jika G tidak terhubung 3, seseorang dapat 3-warna komponen yang terhubung 3 secara mandiri.
David Eppstein
24

S3

Gil Kalai
sumber