ในทฤษฎีกราฟทฤษฎีบทของ Vizingกล่าวว่ากราฟแบบไม่มีทิศทาง อย่างง่ายทุกกราฟ สามารถระบายสีขอบได้โดยใช้จำนวนสีที่มากกว่าดีกรี สูงสุด Δของกราฟไม่เกินหนึ่งสี จำเป็นต้องใช้สีอย่างน้อยΔสีเสมอ ดังนั้นกราฟแบบไม่มีทิศทางจึงสามารถแบ่งออกเป็นสองประเภท ได้แก่ กราฟ "ประเภทที่หนึ่ง" ซึ่งใช้ สี Δสีก็เพียงพอ และกราฟ "ประเภทที่สอง" ซึ่ง ต้องใช้สี Δ + 1สี ทฤษฎีบทของ Vizing ในรูปแบบทั่วไปกล่าวว่ามัลติกราฟ แบบไม่มีทิศทางทุกกราฟ ที่ไม่มีวงวนสามารถระบายสีได้ด้วยสีไม่เกินΔ+µสี โดยที่µคือความซ้ำซ้อนของมัลติกราฟ^{[ 1 ]}ทฤษฎีบทนี้ตั้งชื่อตามVadim G. Vizingผู้ตีพิมพ์ในปี 1964

ทฤษฎีบทที่ค้นพบโดยนักคณิตศาสตร์ชาวโซเวียตVadim G. Vizingได้รับการตีพิมพ์ในปี 1964 ขณะที่ Vizing ทำงานอยู่ที่โนโวซีบีร์สค์^{[ 2 ] [ 3 ]}และกลายเป็นที่รู้จักในชื่อทฤษฎีบทของ Vizing นักคณิตศาสตร์ชาวอินเดีย RP Gupta ค้นพบทฤษฎีบทนี้โดยอิสระในระหว่างที่กำลังทำวิทยานิพนธ์ปริญญาเอก (1965-1967) ^{[ 4 ] [ 5 ]}

เมื่อΔ = 1กราฟGจะต้องเป็นกราฟจับคู่ (matching graph) โดยไม่มีขอบสองขอบใดอยู่ติดกัน และจำนวนสีของขอบ (edge ​​chromatic number) เท่ากับหนึ่ง นั่นคือ กราฟทั้งหมดที่มีΔ( G ) = 1จัดอยู่ในกลุ่มกราฟชั้นที่หนึ่ง (class one)

เมื่อΔ = 2กราฟGจะต้องเป็นการรวมกันแบบไม่ทับซ้อนกันของเส้นทางและวงจรถ้าวงจรทั้งหมดเป็นวงจรคู่ ก็สามารถระบายสีขอบด้วย 2 สีได้โดยการสลับสีสองสีรอบแต่ละวงจร อย่างไรก็ตาม ถ้ามีวงจรคี่อย่างน้อยหนึ่งวงจร ก็จะไม่สามารถระบายสีขอบด้วย 2 สีได้ กล่าวคือ กราฟที่มีΔ = 2จะเป็นกราฟระดับหนึ่งก็ต่อเมื่อเป็นกราฟสองส่วน เท่านั้น

หลักฐานนี้ได้รับแรงบันดาลใจจากDiestel (2000 ) ^{[ 6 ]}

ให้G  =  ( V , E ) เป็นกราฟแบบไม่มีทิศทางอย่างง่าย เราจะดำเนินการโดยใช้การอุปมานบนmซึ่งเป็นจำนวนขอบ ถ้ากราฟว่างเปล่า ทฤษฎีบทนี้จะเป็นจริงโดยปริยาย ให้m >  0  และ สมมติว่ามีการระบายสีขอบแบบ (Δ+1)ที่เหมาะสมสำหรับทุกG − xy  โดยที่xy ∈ E  

เรากล่าวว่าสีα ∈ {1,...,Δ+1   } หายไปในx ∈ V  เมื่อเทียบกับการระบายสีขอบ แบบ (Δ+1) ที่เหมาะสม cถ้าc ( xy ) ≠ α  สำหรับทุกy ∈ N( x )  นอกจากนี้ ให้α / β -path จากxแทนเส้นทางสูงสุดที่ไม่ซ้ำกันซึ่งเริ่มต้นในxด้วย ขอบที่ระบายสี αและสลับสีของขอบ (ขอบที่สองมีสีβขอบที่สามมีสีαและอื่นๆ) ความยาวของเส้นทางอาจเป็น0โปรดทราบว่าถ้าcเป็นการระบายสีขอบแบบ(Δ+1) ที่เหมาะสมของ Gแล้วทุกจุดยอดจะมีสีที่หายไปเมื่อเทียบกับc

สมมติว่าไม่มีการระบายสีขอบ(Δ+1) ที่เหมาะสมของ Gอยู่ ซึ่งเทียบเท่ากับข้อความนี้:

(1) ให้xy ∈ E  และcเป็นการระบายสีขอบ(Δ+1) ที่เหมาะสมใดๆ ของ G − xy  และαหายไปจากxและβหายไปจากyเมื่อเทียบกับcแล้ว เส้นทาง α / βจากyสิ้นสุดที่x

สิ่งนี้เทียบเท่ากัน เพราะถ้า (1) ไม่เป็นจริง เราสามารถสลับสีαและβบน เส้นทาง α / βและกำหนดสีของxyให้เป็นαซึ่งจะสร้างการระบายสีขอบ(Δ+1) ที่เหมาะสมของ Gจากcในทางกลับกัน ถ้ามีการระบายสีขอบ(Δ+1) ที่เหมาะสมอยู่ เราสามารถลบ xyจำกัดการระบายสี และ (1) ก็จะไม่เป็นจริงเช่นกัน

ตอนนี้ ให้xy ∈ E  และc เป็นการระบายสีขอบ ที่เหมาะสม (Δ+1) ของ G − xy   และαหายไปในxเมื่อเทียบกับc เรากำหนดy ,..., y ให้เป็นลำดับสูงสุดของเพื่อนบ้านของx โดยที่c ( xy )หายไปในy เมื่อเทียบกับc สำหรับทุก0  < i ≤ k   

เรากำหนดสีc ,..., c ดังนี้

c ( xy )= c ( xy )สำหรับทุก 0 ≤ j < i     ,

c ( xy )ไม่ได้ถูกกำหนด

c ( e )= c ( e ) otherwise.

ดังนั้นc จึงเป็นการระบายสีขอบ(Δ+1) ที่เหมาะสมของ G − xy   เนื่องจากนิยามของy ,..., y นอกจากนี้ โปรดสังเกตว่าสีที่หายไปในx นั้นเหมือนกันเมื่อเทียบกับc สำหรับทุก0 ≤ i ≤ k    

ให้βเป็นสีที่หายไปในy เมื่อเทียบกับc แล้วβก็หายไปในy เมื่อเทียบกับc สำหรับทุก0 ≤ i ≤ k    ด้วย โปรดสังเกตว่าβไม่สามารถหายไปในxได้ มิฉะนั้นเราจะสามารถขยายc ได้อย่างง่ายดาย ดังนั้นขอบที่มีสีβจึงเชื่อมต่อกับxสำหรับทุกc จากคุณสมบัติสูงสุดของkจะมี1 ≤ i < k    ที่ทำให้c ( xy )  = β จากนิยามของc ,..., c จะได้ว่า:

c ( xy )  = c ( xy ) = c ( xy ) = β     

ให้Pเป็น เส้นทาง α / βจากy โดยสัมพันธ์กับc จาก (1) เส้นทางPจะต้องสิ้นสุดที่xแต่αหายไปในxดังนั้นจึงต้องสิ้นสุดด้วยขอบที่มีสีβด้วยเหตุนี้ ขอบสุดท้ายของPคือy xตอนนี้ ให้P'เป็น เส้นทาง α / βจากy โดยสัมพันธ์กับc เนื่องจากP'ถูกกำหนดอย่างไม่ซ้ำกัน และขอบภายในของPไม่เปลี่ยนแปลงในc ,..., c เส้นทางP'จึงใช้ขอบเดียวกันกับPในลำดับย้อนกลับและผ่านy ขอบที่นำไปสู่​​y มีสีα อย่างชัดเจน แต่βหายไปในy ดังนั้นP'จึงสิ้นสุดที่y ซึ่งขัดแย้งกับ (1) ข้างต้น

ผู้เขียนหลายคนได้เสนอเงื่อนไขเพิ่มเติมที่จัดประเภทกราฟบางกราฟให้เป็นคลาสหนึ่งหรือคลาสสอง แต่ไม่ได้ให้การจัดประเภทที่สมบูรณ์ ตัวอย่างเช่น หากจุดยอดที่มีดีกรีสูงสุดΔในกราฟGก่อตัวเป็นเซตอิสระหรือโดยทั่วไปแล้ว หากกราฟย่อยที่เหนี่ยวนำสำหรับเซตของจุดยอดนี้เป็นป่า กราฟGจะต้องเป็นคลาสหนึ่ง^{[ 7 ]}

Erdős & Wilson (1977)แสดงให้เห็นว่า กราฟ เกือบทั้งหมดเป็นกราฟคลาสหนึ่ง นั่นคือ ในแบบจำลอง Erdős–Rényiของกราฟสุ่มซึ่ง กราฟ nจุดยอดทั้งหมดมีโอกาสเท่ากัน ให้p ( n )เป็นความน่าจะเป็นที่ กราฟ nจุดยอดที่ดึงมาจากการแจกแจงนี้เป็นกราฟคลาสหนึ่ง จากนั้นp ( n )จะเข้าใกล้หนึ่งในลิมิตเมื่อnเข้าสู่อินฟินิตี้^{[ 8 ]}สำหรับขอบเขตที่แม่นยำยิ่งขึ้นเกี่ยวกับอัตราที่p ( n )ลู่เข้าสู่หนึ่ง โปรดดูFrieze et al. (1988 ) ^{[ 9 ]}

ปัญหาการจำแนกประเภททั่วไปของกราฟเป็นคลาสหนึ่งหรือคลาสสองได้รับการแสดงให้เห็นในปี พ.ศ. 2524 ว่าเป็นปัญหาNP- complete ^{[ 10 ]}

วิซิง (1965)แสดงให้เห็นว่ากราฟระนาบเป็นกราฟชั้นหนึ่งก็ต่อเมื่อดีกรีสูงสุดของมันอย่างน้อยแปด ในทางตรงกันข้าม เขาตั้งข้อสังเกตว่าสำหรับดีกรีสูงสุดใดๆ ในช่วงตั้งแต่สองถึงห้า จะมีกราฟระนาบชั้นสองอยู่ สำหรับดีกรีสอง วงจรคี่ใดๆ ก็เป็นกราฟดังกล่าว และสำหรับดีกรีสาม สี่ และห้า กราฟเหล่านี้สามารถสร้างขึ้นจากทรงหลายเหลี่ยมเพลโตได้โดยการแทนที่ขอบเดี่ยวด้วยเส้นทางของขอบที่อยู่ติดกันสองขอบ

ในข้อสันนิษฐานกราฟระนาบของ Vizing นั้น Vizing (1965)ระบุว่ากราฟระนาบแบบง่ายทั้งหมดที่มีดีกรีสูงสุดหกหรือเจ็ดเป็นกราฟระดับหนึ่ง ซึ่งเป็นการปิดกรณีที่เป็นไปได้ที่เหลืออยู่Zhang (2000)และSanders & Zhao (2001)ได้พิสูจน์ข้อสันนิษฐานกราฟระนาบของ Vizing บางส่วนโดยอิสระ โดยแสดงให้เห็นว่ากราฟระนาบทั้งหมดที่มีดีกรีสูงสุดเจ็ดเป็นกราฟระดับหนึ่ง^{[ 11 ] [ 12 ]} ดังนั้น กรณีเดียวของข้อสันนิษฐานที่ยังไม่ได้รับการแก้ไขคือกรณีที่มีดีกรีสูงสุดหก ข้อสันนิษฐานนี้มีนัยสำคัญต่อ ข้อ สันนิษฐานการระบายสีทั้งหมด

กราฟระนาบของคลาสสองที่สร้างขึ้นโดยการแบ่งย่อยของทรงหลายเหลี่ยมเพลโตนั้นไม่ปกติ: พวกมันมีจุดยอดที่มีดีกรีสองเช่นเดียวกับจุดยอดที่มีดีกรีสูงกว่าทฤษฎีบทสี่สี (พิสูจน์โดยAppel & Haken (1976) ) เกี่ยวกับการระบายสีจุดยอดของกราฟระนาบ^{[ 13 ]}เทียบเท่ากับข้อความที่ว่ากราฟระนาบปกติ 3 ที่ไม่มีสะพานทุกกราฟเป็นคลาสหนึ่ง^{[ 14 ]}

ในปี 1969 บรังโก กรูนบอม ตั้งข้อสันนิษฐานว่ากราฟ 3-ปกติทุกกราฟที่มีการฝังแบบทรงหลายเหลี่ยมบนแมนิโฟลด์แบบมี ทิศทางสองมิติใดๆ เช่นโทรัสจะต้องเป็นกราฟระดับหนึ่ง ในบริบทนี้ การฝังแบบทรงหลายเหลี่ยมคือการฝังกราฟที่ทุกหน้าของการฝังเป็นดิสก์ในเชิงโทโพโลยี และกราฟคู่ของการฝังนั้นเป็นกราฟแบบง่าย ไม่มีวงวนในตัวเองหรือการเชื่อมต่อหลายจุด หากเป็นจริง นี่จะเป็นการขยายความของทฤษฎีบทสี่สี ซึ่งไทต์ได้แสดงให้เห็นว่าเทียบเท่ากับข้อความที่ว่ากราฟ 3-ปกติที่มีการฝังแบบทรงหลายเหลี่ยมบนทรงกลมเป็นกราฟระดับหนึ่ง อย่างไรก็ตามโคโคล (2009)ได้แสดงให้เห็นว่าข้อสันนิษฐานนี้เป็นเท็จโดยการค้นพบสนาร์กที่มีการฝังแบบทรงหลายเหลี่ยมบนพื้นผิวแบบมีทิศทางที่มีจีนัสสูง^{[ 15 ]}จากโครงสร้างนี้ เขายังแสดงให้เห็นว่าการบอกว่ากราฟที่ฝังตัวแบบหลายเหลี่ยมเป็นกราฟชั้นหนึ่งนั้นเป็นปัญหา NP-complete ^{[ 16 ]}

เนื่องจากปัญหาการจำแนกประเภททั่วไป ไม่ว่าจะเป็นคลาสหนึ่งหรือคลาสสอง เป็นปัญหา NP-complete จึงไม่มีหวังที่จะมีอัลกอริทึมแบบใช้เวลาพหุนามสำหรับการระบายสีขอบที่ดีที่สุด อย่างไรก็ตาม การพิสูจน์ทฤษฎีบทดั้งเดิมของ Vizing นั้นเป็นอัลกอริทึมอยู่แล้ว โดยอธิบายถึงอัลกอริทึมแบบใช้เวลาพหุนามสำหรับการระบายสีขอบของกราฟใดๆ ด้วย สี Δ + 1สี โดยที่Δคือดีกรีสูงสุดของกราฟ นั่นคือ อัลกอริทึมใช้จำนวนสีที่เหมาะสมที่สุดสำหรับกราฟคลาสสอง และใช้สีมากกว่าที่จำเป็นไม่เกินหนึ่งสีสำหรับกราฟทั้งหมด โดยเริ่มจากกราฟที่ยังไม่ได้ระบายสี จากนั้นจึงค้นหาวิธีการระบายสีกราฟซ้ำๆ เพื่อเพิ่มจำนวนขอบที่ระบายสีขึ้นหนึ่งขอบ อัลกอริทึมจึงระบายสีกราฟ${\displaystyle m}$ขอบ โดยการเปลี่ยนสีแต่ละครั้งจะใช้เวลา${\displaystyle O(n)}$เวลา ส่งผลให้มีความซับซ้อนด้านเวลาโดยรวมเท่ากับ${\displaystyle O(mn)}$.

Misra & Gries (1992)อธิบายอัลกอริทึมที่ใช้กลยุทธ์เดียวกันกับอัลกอริทึมดั้งเดิมของ Vizing โดยเฉพาะอย่างยิ่ง สมมติว่าuvเป็นขอบที่ไม่มีสีในกราฟที่มีสีบางส่วน อัลกอริทึมของ Misra และ Gries อาจตีความได้ว่าเป็นการสร้างpseudoforest แบบมีทิศทาง P (กราฟที่แต่ละจุดยอดมีขอบขาออกอย่างมากที่สุดหนึ่งเส้น) บนจุดข้างเคียงของu : สำหรับจุดข้างเคียงp แต่ละจุด ของuอัลกอริทึมจะหาค่าสีcที่ไม่ได้ถูกใช้โดยขอบใดๆ ที่เชื่อมต่อกับpหาจุดยอดq (ถ้ามี) ที่ขอบuqมีสีcและเพิ่มpqเป็นขอบในPมีสองกรณี:

• หากป่าเทียมPที่สร้างขึ้นในลักษณะนี้มีเส้นทางจากvไปยังจุดยอดwที่ไม่มีขอบขาออกในPแล้วจะมีสีcที่ใช้ได้ทั้งที่uและwการเปลี่ยนสีขอบuwด้วยสีcจะทำให้สีของขอบที่เหลือเลื่อนไปหนึ่งขั้นตามเส้นทางนี้: สำหรับแต่ละจุดยอดpในเส้นทาง ขอบupจะใช้สีที่เคยใช้โดยจุดยอดถัดไปของpในเส้นทาง ซึ่งนำไปสู่การระบายสีใหม่ที่รวมถึงขอบuvด้วย^{[ 17 ]}
• ในทางกลับกัน หากเส้นทางที่เริ่มต้นจากvในป่าเทียมPนำไปสู่วงจร ให้wเป็นเพื่อนบ้านของuที่เส้นทางเชื่อมต่อกับวงจร ให้cเป็นสีของขอบuwและให้dเป็นสีที่ไม่ได้ใช้โดยขอบใดๆ ที่จุดยอดuจากนั้นการสลับสีcและdบนโซ่ Kempeจะทำลายวงจรหรือขอบที่เส้นทางเชื่อมต่อกับวงจร ทำให้เกิดกรณีข้างต้น^{[ 17 ]}

ด้วยโครงสร้างข้อมูลอย่างง่ายบางอย่างเพื่อติดตามสีที่ใช้และพร้อมใช้งานที่แต่ละจุดยอด การสร้างPและขั้นตอนการระบายสีใหม่ของอัลกอริทึมสามารถดำเนินการได้ในเวลาO( n )โดยที่nคือจำนวนจุดยอดในกราฟอินพุต เนื่องจากขั้นตอนเหล่านี้ต้องทำซ้ำmครั้ง โดยแต่ละครั้งจะเพิ่มจำนวนขอบที่ระบายสีขึ้นหนึ่งขอบ เวลาทั้งหมดจึงเป็นO ( mn ) ^{[ 17 ]}

ในรายงานทางเทคนิคที่ยังไม่ได้ตีพิมพ์Gabow et al. (1985)อ้างว่ามีความเร็วมากกว่า${\displaystyle O(m{\sqrt {n}}\log n)}$ขอบเขตเวลาสำหรับปัญหาเดียวกันของการระบายสีด้วย สี Δ + 1สี^{[ 18 ]}ขอบเขตเดียวกันนี้ยังปรากฏในบทความปี 1982 โดย Arjomandi ^{[ 19 ]}

ในปี 2024 มีการพัฒนาอัลกอริทึมที่ได้รับการปรับปรุงหลายอย่าง โดยอัลกอริทึมที่ได้ผลลัพธ์สุดท้ายคือ อัลกอริทึม เวลาแบบกึ่งเชิงเส้น เชิงความน่าจะ เป็น ซึ่งมี${\displaystyle O(m\log \Delta )={\widetilde {O}}(m)}$ความซับซ้อนของเวลา^{[ 20 ] [ 21 ]}

ในทั้งGutin & Toft (2000)และSoifer (2008) Vizing กล่าวถึงว่างานของเขาได้รับแรงบันดาลใจจากทฤษฎีบทของShannon (1949) ^{[ 22 ]}ที่แสดงให้เห็นว่ามัลติกราฟสามารถระบายสีได้ด้วยสีไม่เกิน(3/2)Δสี^{[ 23 ] [ 24 ]}แม้ว่าทฤษฎีบทของ Vizing จะเป็นเนื้อหามาตรฐานในตำราทฤษฎีกราฟหลายเล่มในปัจจุบัน แต่ Vizing ก็ประสบปัญหาในการตีพิมพ์ผลลัพธ์ในตอนแรก และบทความของเขาเกี่ยวกับเรื่องนี้ปรากฏในวารสารที่ไม่เป็นที่รู้จักDiskret. Analiz . ^{[ 25 ]}

• ทฤษฎีบทของบรู๊คส์ที่เชื่อมโยงการระบายสีจุดยอดกับดีกรีสูงสุด

• การ พิสูจน์ทฤษฎีบทของ Vizingที่PlanetMath