Bukti teorema pewarnaan garis Kőnig ( $\chi'(G) = \Delta(G)$)

Dec 06 2020

Saya mencoba mencari bukti dari teorema pewarnaan garis Kőnig , yaitu:

Indeks kromatik dari setiap graf bipartit sama dengan derajat maksimumnya

Namun yang mengejutkan saya, saya hanya * dapat menemukan dua pertanyaan yang menyentuh subjek:

  • Pewarnaan tepi pada grafik bipartit
  • Pewarnaan tepi graf bipartit dengan derajat maksimum D hanya membutuhkan warna D.

Karena grafik adalah kelemahan saya, saya tidak dapat menggunakan informasi yang terdapat di atas untuk membuktikannya $\chi'(G) = \Delta(G)$ diri.


* Saya telah menemukan banyak makalah yang mengacu padanya, tetapi tidak ada yang membuktikan, kecuali untuk halaman 4 dari CH6.pdf dari pertanyaan pertama, tetapi menurut saya itu tidak cukup.

Jawaban

1 Hendrix Dec 06 2020 at 01:38

Saya akan mencoba dan memberikan gambaran umum tentang pengetahuan prasyarat, dan menyertakan sumber di setiap langkah sehingga Anda dapat memahami secara berurutan. Jika Anda tidak memahami bagian tertentu (seperti konstruksi di akhir), saya sarankan Anda mengerjakan beberapa contoh kecil.

Mari kita perkenalkan Teorema Hall :

Teorema: (Teorema Hall) Let $G$ menjadi grafik bipartit dengan bagian-bagian $A$ dan $B$. Kemudian$G$ memiliki pencocokan (set tepi independen) jenuh $A$ (setiap simpul dari $A$ adalah titik akhir dari beberapa tepi dalam pencocokan) jika dan hanya jika untuk setiap $X \subseteq A$ kita punya $|X| \le |N(X)|$.

Dua sumber yang saya rekomendasikan untuk mendapatkan pandangan yang baik tentang Teorema Hall adalah Teori Graf Diestel (yang, jika saya ingat, memberikan empat bukti) dan Pengantar Teori Graf dari West.

Signifikansi Teorema Hall di sini adalah untuk $k$-grafik bipartit beraturan, kita dapat menemukan kecocokan yang sempurna. Ini berasal dari dua hal:

  1. SEBUAH $k$-Grafik bipartit beraturan seimbang .
  2. SEBUAH $k$-Grafik bipartit beraturan memenuhi kondisi Hall .

Nah sekarang kita bisa buktikan berikut ini:

Lemma: Jika $G$ adalah $k$-Graf bipartit beraturan, lalu $\chi'(G) = k$.

Kita dapat menggunakan induksi $k$. Dengan Teorema Hall,$G$ memiliki kecocokan yang sempurna $M$. Mempertimbangkan$G-M$, yang mana $k-1$-teraturan (mengapa?). Dengan hipotesis induksi,$\chi'(G) = k-1$, dan jadi kami bisa menambahkan $M$ kembali sebagai warna baru, karenanya memperluas hak $k-1$pewarnaan-panji dari $G-M$ ke yang tepat $k$pewarnaan-panji aktif $G$.

Jika Anda tidak terbiasa dengan induksi, berikut penjelasannya yang berbeda: Menghapus pencocokan sempurna dari a $k$-Grafik bipartit beraturan menghasilkan a $k-1$-grafik beraturan, yang juga harus memiliki kecocokan sempurna ... Ulangi proses ini $k$ waktu.

Sekarang untuk garis finis. Kami ingin membuktikan hasil untuk setiap graf bipartit$G$.

Hasil: Jika $G$ adalah grafik bipartit $\chi'(G) = \Delta(G)$.

Jika $G$teratur, lalu kita selesai oleh Lemma. Jika tidak, setidaknya ada satu simpul$v$ di $G$ dengan $\deg(v) < \Delta(G)$. Kita bisa membuat grafik$R$ seperti yang

  1. $R$ adalah bipartit.
  2. $R$ aku s $\Delta(G)$-reguler.
  3. $G \subseteq R$.

Salah satu konstruksinya adalah sebagai berikut. Kita punya$G$ bipartit dengan bagian-bagian $A$ dan $B$. Ambil salinan$G$, katakanlah $G'$ dengan bagian $A'$ dan $B'$. Kemudian untuk setiap simpul$v$ bukan derajat $\Delta(G)$ di $G$, kami menambahkan keunggulan di antara $v$ dan itu salinan $v' \in G'$. Grafik yang baru diperoleh ini bipartit dengan bagian-bagian$A \cup B'$ dan $B \cup A'$. Ulangi proses ini seperlunya. Anda akan melihat bahwa pada setiap iterasi jarak antara derajat minimum dan derajat maksimum berkurang, jadi kita harus mengakhiri dengan a$\Delta(G)$grafik beraturan $R$seperti yang diinginkan. Anda akan menemukan konstruksi ini adalah yang diberikan oleh komentar Jon Noel di sini .

Menggunakan Lemma, $\chi'(R) = \Delta(G)$, dan dengan demikian ada yang benar $\Delta(G)$pewarnaan-panji dari $R$. Sejak$G \subseteq R$, pewarnaan yang tepat ini bekerja untuk $G$. Yaitu$\chi'(G) = \Delta(G)$.


Beberapa catatan.

Perhatikan bahwa kami menggunakan fakta umum itu $\chi'(H) \le \chi'(G)$ untuk $H \subseteq G$ pada akhirnya.

Satu hal yang saya lihat sekilas adalah jika kita mengizinkan banyak sisi, tetapi hal-hal masih berfungsi seperti itu. Jika kami mengizinkan banyak tepi, dapatkah Anda melihat mengapa cara kami membangunnya$R$ mengambil tepat $1$pengulangan? Saya tidak percaya ada alasan nyata untuk mengecualikan penggunaan banyak sisi.

Salah satu kunci yang diambil adalah memikirkan kelas warna dalam pewarnaan tepi sebagaimana adanya: pencocokan.