ในทฤษฎีกราฟการระบายสีขอบที่ถูกต้องของกราฟคือการกำหนด "สี" ให้กับขอบของกราฟ โดยที่ไม่มีขอบสองขอบใดมีสีเดียวกัน ตัวอย่างเช่น รูปทางด้านขวาแสดงการระบายสีขอบของกราฟด้วยสีแดง สีน้ำเงิน และสีเขียว การระบายสีขอบเป็นหนึ่งในหลายประเภทของการระบายสีกราฟปัญหาการระบายสีขอบถามว่า เป็นไปได้หรือไม่ที่จะระบายสีขอบของกราฟที่กำหนดโดยใช้สีที่แตกต่างกันไม่เกินkสี สำหรับค่าk ที่กำหนด หรือใช้สีน้อยที่สุดเท่าที่จะเป็นไปได้ จำนวนสีขั้นต่ำที่จำเป็นสำหรับขอบของกราฟที่กำหนดเรียกว่าดัชนีสีของกราฟ

ตามทฤษฎีบทของ Vizingจำนวนสีที่จำเป็นสำหรับการระบายสีขอบของกราฟแบบง่ายจะเป็นค่า สูงสุด ΔหรือΔ+1สำหรับกราฟบางประเภท เช่นกราฟสองส่วน และ กราฟระนาบที่มีดีกรีสูงจำนวนสีจะเป็นΔ เสมอ และสำหรับกราฟหลายส่วนจำนวนสีอาจมากถึง3Δ/2มีอัลกอริทึมที่ใช้เวลาในการประมวลผลแบบพหุนามที่สร้างการระบายสีที่เหมาะสมที่สุดสำหรับกราฟสองส่วน และการระบายสีกราฟแบบง่ายที่ไม่ใช่กราฟสองส่วนโดยใช้สีไม่เกินΔ+1สี อย่างไรก็ตาม ปัญหาทั่วไปของการหาการระบายสีขอบที่เหมาะสมที่สุดเป็นปัญหาNP-hardและอัลกอริทึมที่เร็วที่สุดที่รู้จักใช้เวลาแบบเลขชี้กำลัง มีการศึกษาปัญหาการระบายสีขอบหลายรูปแบบ ซึ่งการกำหนดสีให้กับขอบต้องเป็นไปตามเงื่อนไขอื่นนอกเหนือจากการไม่ติดกัน การระบายสีขอบมีการประยุกต์ใช้ในปัญหาการจัดตารางเวลาและการจัดสรรความถี่สำหรับเครือข่าย ใยแก้วนำแสง

กราฟวงจรอาจมีขอบที่ระบายสีด้วยสองสีหากความยาวของวงจรเป็นเลขคู่: เพียงแค่สลับสีทั้งสองรอบวงจร อย่างไรก็ตาม หากความยาวเป็นเลขคี่ จะต้องใช้สามสี^{[ 1 ]}

กราฟสมบูรณ์K _nที่มีnจุดยอด สามารถระบายสีขอบได้ด้วยn − 1สี เมื่อnเป็นจำนวนคู่ ซึ่งเป็นกรณีพิเศษของทฤษฎีบทของ Baranyai Soifer (2008)ได้เสนอการสร้างทางเรขาคณิตของการระบายสีในกรณีนี้ดังนี้: วาง จุด nจุดที่จุดยอดและจุดศูนย์กลางของรูปหลายเหลี่ยมปกติ ที่มีด้าน ( n − 1)ด้าน สำหรับแต่ละชั้นสี ให้รวมขอบหนึ่งเส้นจากจุดศูนย์กลางไปยังจุดยอดของรูปหลายเหลี่ยมจุดใดจุดหนึ่ง และขอบตั้งฉากทั้งหมดที่เชื่อมต่อจุดยอดของรูปหลายเหลี่ยมเป็นคู่ๆ อย่างไรก็ตาม เมื่อnเป็นจำนวนคี่ จะต้องใช้ nสี: แต่ละสีสามารถใช้ได้กับขอบ เพียง ( n − 1)/2 เส้น ซึ่งเป็นเศษส่วน 1/ nของทั้งหมด^{[ 2 ]}

นักวิจัยหลายท่านได้ศึกษาการระบายสีขอบของกราฟคี่ซึ่งเป็น กราฟปกติ n-มิติ ที่จุดยอดแทนทีม ผู้เล่น n − 1คน ที่เลือกจากกลุ่ม ผู้เล่น 2n − 1คน และขอบแทนการจับคู่ที่เป็นไปได้ของทีมเหล่านี้ (โดยมีผู้เล่นหนึ่งคนเหลือเป็น "คนนอก" เพื่อทำหน้าที่เป็นกรรมการตัดสินเกม) กรณีที่n = 3 จะได้ กราฟ Petersenที่เป็นที่รู้จักกันดีดังที่Biggs (1972)อธิบายปัญหา (สำหรับn = 6 ) ผู้เล่นต้องการหาสตารางการแข่งขันสำหรับการจับคู่เหล่านี้ โดยที่แต่ละทีมจะเล่นเกมทั้งหกเกมในวันต่างๆ ของสัปดาห์ โดยทุกทีมได้หยุดพักในวันอาทิตย์ กล่าวคือ หากกำหนดปัญหาอย่างเป็นทางการทางคณิตศาสตร์ พวกเขาต้องการหาการระบายสีขอบ 6 สีของกราฟคี่ปกติ6 _มิติO6เมื่อnเป็น 3, 4 หรือ 8 การระบายสีขอบของOn _nต้องใช้ สี n + 1สี แต่เมื่อเป็น 5, 6 หรือ 7 จะต้องใช้สี เพียง n สีเท่านั้น ^{[ 3 ]}

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

การระบายสีขอบที่เหมาะสมด้วย สีที่แตกต่างกัน kสี เรียกว่า การระบายสีขอบแบบ k สี (proper k -edge-coloring) กราฟที่สามารถกำหนดการ ระบายสีขอบ แบบ k สีได้ เรียกว่า กราฟที่สามารถระบายสีขอบ แบบ k สีได้ (k-edge _- colorable) จำนวนสีน้อยที่สุดที่จำเป็นในการระบายสีขอบที่เหมาะสมของกราฟGคือดัชนีสีหรือ จำนวนสีขอบχ′( G )ดัชนีสีบางครั้งเขียนโดยใช้สัญลักษณ์χ₁ ( G ) ด้วย ในสัญลักษณ์นี้ ตัวห้อยหนึ่งแสดงว่าขอบเป็นวัตถุหนึ่งมิติ กราฟจะเป็นกราฟ ที่มีการระบายสีขอบแบบ kสี ถ้าดัชนีสีของกราฟเท่ากับk พอดี ดัชนีสีไม่ควรสับสนกับจำนวนสีχ( G )หรือχ₀ ( G ) ซึ่งเป็น _{จำนวน}สีขั้นต่ำที่จำเป็นในการระบายสีจุดยอดที่เหมาะสม  ของ G

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

การจับคู่ในกราฟGคือเซตของเส้นขอบที่ไม่มีเส้นขอบสองเส้นใดอยู่ติดกันการจับคู่สมบูรณ์คือการจับคู่ที่รวมเส้นขอบที่สัมผัสกับจุดยอดทั้งหมดของกราฟ และการจับคู่สูงสุดคือการจับคู่ที่รวมเส้นขอบให้มากที่สุดเท่าที่จะเป็นไปได้ ในการระบายสีเส้นขอบ เซตของเส้นขอบที่มีสีเดียวกันจะต้องไม่อยู่ติดกันทั้งหมด เพื่อให้เกิดการจับคู่ กล่าวคือ การระบายสีเส้นขอบที่เหมาะสมก็คือการแบ่งกราฟออกเป็นการจับคู่ที่ไม่ซ้ำกันนั่นเอง

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

สำหรับกราฟปกติที่มีดีกรีkที่ไม่มีการจับคู่ที่สมบูรณ์แบบ ขอบเขตล่างนี้สามารถใช้เพื่อแสดงว่าต้องใช้สี อย่างน้อย k + 1 สี ^{[ 4 ]}โดยเฉพาะอย่างยิ่ง สิ่งนี้เป็นจริงสำหรับกราฟปกติที่มีจำนวนจุดยอดเป็นเลขคี่ (เช่น กราฟสมบูรณ์เลขคี่) สำหรับกราฟดังกล่าว ตาม เล มมาการจับมือkจะต้องเป็นเลขคู่ อย่างไรก็ตาม อสมการχ′ ≥ m /βไม่ได้อธิบายดัชนีสีของกราฟปกติทุกกราฟอย่างสมบูรณ์ เนื่องจากมีกราฟปกติที่มีการจับคู่ที่สมบูรณ์แบบ แต่ไม่ สามารถระบายสีขอบด้วย kสีได้ ตัวอย่างเช่นกราฟ Petersenเป็นกราฟปกติที่มีm = 15และมีβ = 5ขอบในการจับคู่ที่สมบูรณ์แบบ แต่ไม่มีการระบายสีขอบด้วย 3 สี

จำนวนสีของขอบกราฟGมีความสัมพันธ์อย่างใกล้ชิดกับดีกรีสูงสุดΔ( G )ซึ่งเป็นจำนวนขอบที่มากที่สุดที่เชื่อมต่อกับจุดยอดใดจุดหนึ่งของGเห็นได้ชัดว่าχ′( G ) ≥ Δ( G )เพราะถ้า มีขอบที่แตกต่างกัน Δขอบมาบรรจบกันที่จุดยอดv เดียวกัน ขอบเหล่านั้นจะต้องถูกกำหนดสีที่แตกต่างกัน ซึ่งจะเป็นไปได้ก็ต่อเมื่อมีสีอย่างน้อยΔสีให้เลือกใช้ทฤษฎีบทของ Vizing (ตั้งชื่อตามVadim G. Vizingผู้ตีพิมพ์ในปี 1964) ระบุว่าขอบเขตนี้ค่อนข้างแน่นหนา: สำหรับกราฟใดๆ จำนวนสีของขอบจะเป็นΔ( G )หรือΔ( G ) + 1เมื่อχ′( G ) = Δ( G )กราฟGจะถูกเรียกว่าเป็นกราฟคลาส 1 มิเช่นนั้นจะถูกเรียกว่าเป็นกราฟคลาส 2

กราฟสองส่วนทุกกราฟเป็นกราฟคลาส 1 ^{[ 5 ]}และกราฟสุ่มเกือบทั้งหมด เป็นกราฟคลาส 1 ^{[ 6 ]} อย่างไรก็ตาม การพิจารณาว่ากราฟใดๆ เป็นกราฟคลาส 1 หรือไม่นั้นเป็น ปัญหา NP-complete ^{[ 7 ]}

Vizing (1965)พิสูจน์ว่ากราฟระนาบที่มีดีกรีสูงสุดอย่างน้อยแปดเป็นกราฟชั้นหนึ่ง และตั้งข้อสันนิษฐานว่ากราฟระนาบที่มีดีกรีสูงสุดเจ็ดหรือหกก็เป็นเช่นเดียวกัน ในทางกลับกัน มีกราฟระนาบที่มีดีกรีสูงสุดตั้งแต่สองถึงห้าที่เป็นกราฟชั้นสอง ข้อสันนิษฐานนี้ได้รับการพิสูจน์แล้วสำหรับกราฟที่มีดีกรีสูงสุดเจ็ด^{[ 8 ]}กราฟลูกบาศก์ระนาบที่ไม่มีสะพานทั้งหมดเป็นกราฟชั้น 1 ซึ่งเป็นรูปแบบที่เทียบเท่ากับทฤษฎีบทสี่สี^{[ 9 ]}

การแยกตัวประกอบ 1ของกราฟปกติkตัวคือการแบ่งขอบของกราฟออกเป็นส่วนจับคู่ที่สมบูรณ์แบบซึ่งก็คือ การระบายสีขอบ kสีของกราฟนั่นเอง กล่าวคือ กราฟปกติจะมีการแยกตัวประกอบ 1 ก็ต่อเมื่อเป็นกราฟระดับ 1 เท่านั้น ในกรณีพิเศษ การระบายสีขอบ 3 สีของ กราฟ ลูกบาศก์ (กราฟปกติ 3 ตัว) บางครั้งเรียกว่าการระบายสีแบบเทต (Tait coloring )

ไม่ใช่ว่ากราฟปกติทุกกราฟจะมีแฟกทอรี 1-ตัวประกอบ ตัวอย่างเช่นกราฟปีเตอร์เซนไม่มี โดยทั่วไปแล้ว กราฟสนา ร์คถูกนิยามว่าเป็นกราฟที่เหมือนกับกราฟปีเตอร์เซน คือไม่มีสะพานเชื่อม เป็นกราฟปกติ 3-ตัวประกอบ และอยู่ในคลาส 2

ตามทฤษฎีบทของKőnig (1916)กราฟปกติแบบสองส่วนทุกกราฟมีการแยกตัวประกอบ 1 ตัว ทฤษฎีบทนี้เคยกล่าวไว้ก่อนหน้านี้ในแง่ของการกำหนดค่าเชิงโปรเจกทีฟและได้รับการพิสูจน์โดยErnst Steinitz

สำหรับมัลติกราฟซึ่งอาจมีขอบขนานหลายเส้นเชื่อมต่อจุดยอดสองจุดเดียวกัน ผลลัพธ์ที่คล้ายคลึงกันแต่มีกำลังอ่อนกว่าทฤษฎีบทของวิซิงเป็นที่ทราบกันดีอยู่แล้ว โดยเกี่ยวข้องกับจำนวนสีของขอบ χ′( G )ระดับสูงสุดΔ( G )และความหลากหลายμ( G )ซึ่งเป็นจำนวนขอบสูงสุดในกลุ่มขอบขนานใดๆ ตัวอย่างง่ายๆ ที่แสดงให้เห็นว่าทฤษฎีบทของวิซิงไม่สามารถใช้ได้กับมัลติกราฟ คือ พิจารณามัลติกราฟของแชนนอน ซึ่งเป็นมัลติกราฟที่มีจุดยอดสามจุดและกลุ่ม ขอบขนาน μ( G ) สาม กลุ่มที่เชื่อมต่อจุดยอดแต่ละคู่ทั้งสามคู่ ในตัวอย่างนี้Δ( G ) = 2μ( G ) (แต่ละจุดยอดจะเชื่อมต่อกับกลุ่มขอบขนาน μ( G )เพียง 2 ใน 3 กลุ่มเท่านั้น) แต่จำนวนสีของขอบคือ3μ( G ) (มี ขอบทั้งหมด 3μ( G )ขอบ และขอบสองขอบใดๆ จะอยู่ติดกัน ดังนั้นขอบทั้งหมดจะต้องถูกกำหนดสีที่แตกต่างกัน) ในผลลัพธ์ที่สร้างแรงบันดาลใจให้ Vizing ^{[ 10 ]} Shannon (1949)แสดงให้เห็นว่านี่คือกรณีที่เลวร้ายที่สุด: χ′( G ) ≤ (3/2)Δ( G )สำหรับมัลติกราฟG ใดๆ นอกจากนี้ สำหรับมัลติกราฟG ใดๆ χ ′( G ) ≤ Δ( G ) + μ( G )ซึ่งเป็นอสมการที่ลดลงเหลือทฤษฎีบทของ Vizing ในกรณีของกราฟแบบง่าย (ซึ่งμ( G ) = 1 )

เนื่องจากปัญหาการทดสอบว่ากราฟเป็นกราฟคลาส 1 หรือไม่นั้นเป็นปัญหาNP-completeจึงไม่มีอัลกอริทึมแบบเวลาพหุนามใดที่รู้จักสำหรับการระบายสีขอบของกราฟทุกกราฟด้วยจำนวนสีที่เหมาะสมที่สุด อย่างไรก็ตาม มีอัลกอริทึมจำนวนหนึ่งที่ได้รับการพัฒนาขึ้นโดยผ่อนปรนเกณฑ์เหล่านี้อย่างน้อยหนึ่งข้อ เช่น อัลกอริทึมเหล่านั้นใช้งานได้เฉพาะกับกราฟบางส่วน หรือไม่ได้ใช้จำนวนสีที่เหมาะสมที่สุดเสมอไป หรือไม่ได้ทำงานในเวลาพหุนามเสมอไป

ในกรณีของกราฟสองส่วนหรือมัลติกราฟที่มีดีกรีสูงสุดΔจำนวนสีที่เหมาะสมที่สุดคือΔพอดีCole, Ost & Schirra (2001)แสดงให้เห็นว่าการระบายสีขอบที่เหมาะสมที่สุดของกราฟเหล่านี้สามารถหาได้ภายในขอบเขตเวลาใกล้เคียงกับเชิงเส้นO( m log Δ)โดยที่mคือจำนวนขอบในกราฟ อัลกอริทึมที่ง่ายกว่า แต่ช้ากว่าเล็กน้อย ได้รับการอธิบายโดยCole & Hopcroft (1982)และAlon (2003)อัลกอริทึมของAlon (2003)เริ่มต้นด้วยการทำให้กราฟอินพุตเป็นกราฟปกติ โดยไม่เพิ่มดีกรีหรือเพิ่มขนาดอย่างมีนัยสำคัญ โดยการรวมคู่ของจุดยอดที่อยู่ในด้านเดียวกันของการแบ่งสองส่วน แล้วเพิ่มจุดยอดและขอบเพิ่มเติมจำนวนเล็กน้อย จากนั้น หากดีกรีเป็นเลขคี่ Alon จะหาการจับคู่ที่สมบูรณ์แบบเพียงจุดเดียวภายในเวลาใกล้เคียงกับเชิงเส้น กำหนดสีให้ และลบออกจากกราฟ ทำให้ดีกรีกลายเป็นเลขคู่ สุดท้ายนี้ อาลอนได้นำข้อสังเกตของกาโบว์ (1976) มาใช้ ซึ่งระบุว่าการเลือกเซตย่อยสลับกันของขอบในเส้นทางออยเลอร์ของกราฟจะแบ่งกราฟนั้นออกเป็นกราฟย่อยปกติสองกราฟ เพื่อแบ่งปัญหาการระบายสีขอบออกเป็นสองปัญหาย่อยที่เล็กกว่า และอัลกอริทึมของเขาจะแก้ปัญหาย่อยทั้งสองนั้นแบบเรียกซ้ำเวลาทั้งหมดของอัลกอริทึมของเขาคือO ( m log m )

สำหรับกราฟระนาบที่มีดีกรีสูงสุดΔ ≥ 7จำนวนสีที่เหมาะสมที่สุดก็คือΔ นั่นเอง และหากสมมติให้Δ ≥ 9 มากขึ้น ก็จะสามารถหาการระบายสีขอบที่เหมาะสมที่สุดได้ในเวลาเชิงเส้น ( Cole & Kowalik 2008 )

สำหรับกราฟ d-regular ซึ่งเป็นกราฟสุ่มเทียมในแง่ที่ว่าเมทริกซ์ประชิด ของกราฟนั้น มีค่า eigenvalue ที่ใหญ่เป็นอันดับสอง (ในค่าสัมบูรณ์) ไม่เกินd ^1−ε โดยที่ d คือจำนวนสีที่เหมาะสมที่สุด ( Ferber & Jain 2020 )

Misra & Gries (1992)และGabow et al. (1985)อธิบายอัลกอริทึมเวลาพหุนามสำหรับการระบายสีกราฟใดๆ ด้วย สี Δ + 1สี ซึ่งตรงตามขอบเขตที่กำหนดโดยทฤษฎีบทของ Vizing ดู อัลกอริทึม การ ระบายสีขอบของ Misra & Gries

สำหรับมัลติกราฟKarloff & Shmoys (1987)นำเสนออัลกอริทึมต่อไปนี้ ซึ่งพวกเขาระบุว่าเป็นผลงานของEli Upfalทำให้มัลติกราฟG เป็นออยเลอร์โดยการเพิ่มจุดยอดใหม่ที่เชื่อมต่อด้วยเส้นขอบกับทุกจุดยอดที่มีดีกรีคี่ ค้นหาเส้นทางออยเลอร์ และเลือกทิศทางสำหรับเส้นทางนั้น สร้างกราฟสองส่วนHซึ่งมีจุดยอดแต่ละจุดของG สองชุด ชุดหนึ่งอยู่แต่ละด้านของการแบ่งสองส่วน โดยมีเส้นขอบจากจุดยอดuทางด้านซ้ายของการแบ่งสองส่วนไปยังจุดยอดvทางด้านขวาของการแบ่งสองส่วน เมื่อใดก็ตามที่เส้นทางที่มีทิศทางมีเส้นขอบจากuไปยังvในGใช้อัลกอริทึมการระบายสีเส้นขอบของกราฟสองส่วนกับHแต่ละชั้นสีในHสอดคล้องกับชุดของเส้นขอบในGที่สร้างกราฟย่อยที่มีดีกรีสูงสุดสอง นั่นคือ การรวมกันที่ไม่ซ้ำกันของเส้นทางและวงจร ดังนั้นสำหรับแต่ละชั้นสีในHจึงสามารถสร้างชั้นสีได้สามชั้นในGเวลาในการทำงานของอัลกอริทึมนี้ถูกจำกัดด้วยเวลาในการระบายสีขอบของกราฟสองส่วนO( m log Δ)โดยใช้อัลกอริทึมของCole, Ost & Schirra (2001)จำนวนสีที่อัลกอริทึมนี้ใช้มีค่าสูงสุด ซึ่งใกล้เคียงกับแต่ไม่เท่ากับขอบเขตของ Shannon ที่นอกจากนี้ยังสามารถทำให้เป็นอัลกอริทึมแบบขนานได้ด้วยวิธีที่ตรงไปตรงมา ในบทความเดียวกัน Karloff และ Shmoys ยังนำเสนออัลกอริทึมแบบใช้เวลาเชิงเส้นสำหรับการระบายสีมัลติกราฟที่มีดีกรีสูงสุดสามด้วยสี่สี (ตรงกับขอบเขตของ Shannon และ Vizing) ซึ่งทำงานบนหลักการที่คล้ายกัน: อัลกอริทึมของพวกเขาเพิ่มจุดยอดใหม่เพื่อให้กราฟเป็นออยเลอร์ ค้นหาเส้นทางออยเลอร์ จากนั้นเลือกชุดขอบสลับกันบนเส้นทางเพื่อแบ่งกราฟออกเป็นสองกราฟย่อยที่มีดีกรีสูงสุดสอง เส้นทางและแม้แต่รอบของแต่ละกราฟย่อยอาจถูกระบายสีด้วยสองสีต่อกราฟย่อย หลังจากขั้นตอนนี้ วงจรคี่ที่เหลือแต่ละวงจะมีขอบอย่างน้อยหนึ่งขอบที่สามารถระบายสีด้วยสีใดสีหนึ่งจากสองสีที่อยู่ในกราฟย่อยฝั่งตรงข้ามได้ การลบขอบนี้ออกจากวงจรคี่จะเหลือเส้นทาง ซึ่งสามารถระบายสีโดยใช้สองสีสำหรับกราฟย่อยนั้นได้ ${\displaystyle 3\left\lceil {\frac {\Delta }{2}}\right\rceil }$${\displaystyle \left\lfloor {\frac {3\Delta }{2}}\right\rfloor }$

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

ผู้เขียนหลายคนได้ตั้งข้อสันนิษฐานที่บ่งชี้ว่าดัชนีสีเศษส่วนของมัลติกราฟใดๆ (ตัวเลขที่สามารถคำนวณได้ในเวลาพหุนามโดยใช้การเขียนโปรแกรมเชิงเส้น ) จะอยู่ภายในหนึ่งจากดัชนีสี^{[ 13 ]}หากข้อสันนิษฐานเหล่านี้เป็นจริง ก็จะเป็นไปได้ที่จะคำนวณตัวเลขที่ไม่คลาดเคลื่อนจากดัชนีสีเกินหนึ่งในกรณีของมัลติกราฟ ซึ่งตรงกับสิ่งที่ทราบผ่านทฤษฎีบทของ Vizing สำหรับกราฟแบบง่าย แม้ว่าจะยังไม่ได้รับการพิสูจน์โดยทั่วไป แต่ข้อสันนิษฐานเหล่านี้เป็นที่ทราบกันว่าเป็นจริงเมื่อดัชนีสีอย่างน้อยเท่ากับซึ่งสามารถเกิดขึ้นได้สำหรับมัลติกราฟที่มีมัลติพลิซิตี้ขนาดใหญ่เพียงพอ^{[ 14 ]}${\displaystyle \Delta +{\sqrt {\Delta /2}}}$

การทดสอบว่ากราฟสามารถระบายสีขอบด้วยสีเดียวหรือสองสีนั้นทำได้ง่าย ดังนั้นกรณีที่ไม่ธรรมดาแรกของการระบายสีขอบคือการทดสอบว่ากราฟมีการระบายสีขอบแบบ 3 สีหรือไม่ ดังที่Kowalik (2009)แสดงให้เห็น เป็นไปได้ที่จะทดสอบว่ากราฟมีการระบายสีขอบแบบ 3 สีหรือไม่ในเวลาO(1.344 ⁿ )โดยใช้พื้นที่พหุนามเท่านั้น แม้ว่าขอบเขตเวลาจะเป็นแบบเลขชี้กำลัง แต่ก็เร็วกว่าการค้นหาแบบใช้กำลังทั้งหมดสำหรับการกำหนดสีให้กับขอบที่เป็นไปได้ทั้งหมดอย่างมีนัยสำคัญกราฟ 3-regular ที่เชื่อมต่อกัน สองทางทุกกราฟที่มี nจุดยอดมี การระบายสีขอบแบบ 3 สีจำนวน O(2 ^{n /2} )ซึ่งทั้งหมดสามารถแสดงรายการได้ในเวลาO(2 ^{n /2} ) (ช้ากว่าเวลาที่ใช้ในการค้นหาการระบายสีเพียงสีเดียวเล็กน้อย) ดังที่เกร็ก คูเปอร์เบิร์กสังเกต กราฟของปริซึมเหนือ รูปหลายเหลี่ยม n /2ด้านมี การระบายสี Ω(2n ^{/ 2} ) (ขอบล่างแทนที่จะเป็นขอบบน) ซึ่งแสดงให้เห็นว่าขอบเขตนี้แน่น^{[ 15 ]}

โดยการใช้อัลกอริธึมที่แม่นยำสำหรับการระบายสีจุดยอดกับกราฟเส้นของกราฟอินพุต จะสามารถระบายสีขอบของกราฟใดๆ ที่มี ขอบ m ได้อย่างเหมาะสม โดยไม่คำนึงถึงจำนวนสีที่ต้องการ ในเวลา2 ^m m ^O(1)และพื้นที่แบบเอกซ์โพเนนเชียล หรือในเวลาO(2.2461 ^m )และพื้นที่แบบพหุนามเท่านั้น ( Björklund, Husfeldt & Koivisto 2009 )

เนื่องจากการระบายสีขอบเป็นปัญหา NP-complete แม้กระทั่งสำหรับสามสี จึงไม่น่าจะสามารถคำนวณได้ด้วยพารามิเตอร์คงที่เมื่อกำหนดพารามิเตอร์ด้วยจำนวนสี อย่างไรก็ตาม มันสามารถคำนวณได้ด้วยพารามิเตอร์อื่นๆ โดยเฉพาะอย่างยิ่งZhou, Nakano & Nishizeki (1996)แสดงให้เห็นว่าสำหรับกราฟที่มีtreewidth wการระบายสีขอบที่เหมาะสมที่สุดสามารถคำนวณได้ในเวลาO( nw (6 w ) ^{w ( w + 1)/2} )ซึ่งเป็นขอบเขตที่ขึ้นอยู่กับw อย่างมาก แต่ขึ้นอยู่กับจำนวน จุดยอด nในกราฟ เพียงเชิงเส้นเท่านั้น

Nemhauser & Park (1991)ได้กำหนดปัญหาการระบายสีขอบเป็นโปรแกรมจำนวนเต็มและอธิบายประสบการณ์ของพวกเขาในการใช้ตัวแก้ปัญหาโปรแกรมจำนวนเต็มเพื่อระบายสีขอบกราฟ อย่างไรก็ตาม พวกเขาไม่ได้ทำการวิเคราะห์ความซับซ้อนของอัลกอริทึมของพวกเขา

กราฟสามารถ ระบายสีขอบได้ k สี อย่างเป็นเอกลักษณ์ หากมีวิธีเดียวในการแบ่งขอบออกเป็นkกลุ่มสี โดยไม่คำนึงถึง การเรียงสับเปลี่ยนที่เป็นไปได้ k ! ของสี สำหรับk ≠ 3 กราฟที่สามารถระบายสีขอบได้ k สี อย่างเป็นเอกลักษณ์มีเพียงเส้นทาง วงจร และดาว เท่านั้น แต่สำหรับk = 3กราฟอื่นๆ ก็สามารถ ระบายสีขอบได้ k สีอย่างเป็นเอกลักษณ์เช่นกัน กราฟที่สามารถระบายสีขอบได้ 3 สีอย่างเป็นเอกลักษณ์ทุกกราฟจะมีวงจรแฮมิลโทเนียน สามวงพอดี (เกิดจากการลบหนึ่งในสามกลุ่มสี) แต่มีกราฟปกติ 3 วงที่มีวงจรแฮมิลโทเนียนสามวงและไม่สามารถระบายสีได้ 3 สีอย่างเป็นเอกลักษณ์ เช่นกราฟปีเตอร์เซนแบบทั่วไปG (6 n + 3, 2)สำหรับn ≥ 2กราฟที่ไม่สามารถระบายสีได้ 3 สีอย่างเป็นเอกลักษณ์ที่ไม่ใช่ระนาบที่รู้จักเพียงกราฟเดียวคือกราฟปีเตอร์เซนแบบทั่วไปG (9,2)และมีการคาดการณ์ว่าไม่มีกราฟอื่นๆ อีก^{[ 16 ]}

Folkman & Fulkerson (1969)ได้ทำการศึกษาลำดับตัวเลขที่ไม่เพิ่มขึ้นm ₁ , m ₂ , m ₃ , ...ซึ่งมีคุณสมบัติว่ามีการระบายสีขอบที่เหมาะสมของกราฟG ที่กำหนดให้ โดยมี ขอบ m ₁เส้นเป็นสีแรก ขอบ m ₂เส้นเป็นสีที่สอง เป็นต้น พวกเขาพบว่า หากลำดับPเป็นไปได้ในแง่นี้ และมากกว่าในลำดับพจนานุกรมมากกว่าลำดับQที่มีผลรวมเท่ากันแล้วQก็เป็นไปได้เช่นกัน เพราะถ้าP > Qในลำดับพจนานุกรมแล้วPสามารถแปลงเป็นQได้โดยลำดับขั้นตอน ซึ่งแต่ละขั้นตอนจะลดตัวเลขm _i ตัวหนึ่ง ลงหนึ่งหน่วยและเพิ่มตัวเลข m _j อีกตัวหนึ่ง ที่i < jขึ้นหนึ่งหน่วย ในแง่ของการระบายสีขอบ โดยเริ่มจากการระบายสีที่ทำให้P เป็นจริง แต่ละขั้นตอนเหล่านี้สามารถทำได้โดยการสลับสีiและjบนสายโซ่ Kempeซึ่งเป็นเส้นทางสูงสุดของขอบที่สลับระหว่างสองสี โดยเฉพาะอย่างยิ่ง กราฟใดๆ ก็มี การระบายสีขอบ ที่เป็นธรรมซึ่งก็คือการระบายสีขอบด้วยจำนวนสีที่เหมาะสมที่สุด โดยที่กลุ่มสีสองกลุ่มใดๆ จะมีขนาดแตกต่างกันไม่เกินหนึ่งหน่วย

ทฤษฎีบทDe Bruijn–Erdősอาจใช้เพื่อถ่ายโอนคุณสมบัติการระบายสีขอบหลายอย่างของกราฟจำกัดไปยังกราฟอนันต์ตัวอย่างเช่น ทฤษฎีบทของ Shannon และ Vizing ที่เชื่อมโยงระดับของกราฟกับดัชนีสีของมัน สามารถขยายไปสู่กราฟอนันต์ได้โดยตรง^{[ 17 ]}

ริชเตอร์ (2011)พิจารณาปัญหาการหาภาพวาดกราฟของกราฟลูกบาศก์ ที่กำหนดให้ โดยมีคุณสมบัติว่าขอบทั้งหมดในภาพวาดมีค่าความชันที่แตกต่างกันสามค่า และไม่มีขอบสองขอบใดอยู่บนเส้นเดียวกัน หากมีภาพวาดดังกล่าวอยู่จริง ค่าความชันของขอบก็สามารถนำมาใช้เป็นสีในการระบายสีขอบแบบ 3 สีได้ ตัวอย่างเช่น การวาดกราฟยูทิลิตี้K _3,3โดยใช้ขอบและเส้นทแยงมุมยาวของรูปหกเหลี่ยมปกติแสดงถึงการระบายสีขอบแบบ 3 สีในลักษณะนี้ ดังที่ริชเตอร์แสดงให้เห็น กราฟสองส่วนแบบง่ายปกติ 3 สี ที่มีการระบายสีแบบเทตที่กำหนดให้ จะมีภาพวาดประเภทนี้ที่แสดงถึงการระบายสีที่กำหนดให้ ก็ต่อเมื่อกราฟนั้นเชื่อมต่อกันด้วยขอบ 3สี สำหรับกราฟที่ไม่ใช่กราฟสองส่วน เงื่อนไขจะซับซ้อนกว่าเล็กน้อย: การระบายสีที่กำหนดสามารถแทนด้วยภาพวาดได้ก็ต่อเมื่อ กราฟ สองส่วนที่มีการปกคลุมสองชั้นนั้นเชื่อมต่อกันด้วยขอบ 3 เส้น และหากการลบขอบคู่ที่มีสีเดียวกันใดๆ ก็ตามนำไปสู่กราฟย่อยที่ยังคงไม่ใช่กราฟสองส่วน เงื่อนไขเหล่านี้สามารถทดสอบได้ง่ายในเวลาพหุนาม อย่างไรก็ตาม ปัญหาของการทดสอบว่ากราฟ 4-regular ที่ระบายสีขอบ 4 เส้นนั้นมีภาพวาดที่มีขอบที่มีความชัน 4 ค่า โดยแทนสีด้วยความชันหรือไม่นั้น เป็นปัญหาที่สมบูรณ์สำหรับทฤษฎีการมีอยู่ของจำนวนจริง ซึ่งเป็นระดับความซับซ้อนที่ยากอย่างน้อยเท่ากับ NP-complete

นอกจากจะเกี่ยวข้องกับดีกรีสูงสุดและจำนวนการจับคู่สูงสุดของกราฟแล้ว ดัชนีสียังมีความสัมพันธ์อย่างใกล้ชิดกับความเป็นป่าเชิงเส้นla( G )ของกราฟGซึ่งเป็นจำนวนป่าเชิงเส้นขั้นต่ำ (การรวมกันของเส้นทางที่ไม่ซ้ำกัน) ที่สามารถแบ่งขอบของกราฟออกเป็นส่วนๆ ได้ การจับคู่เป็นป่าเชิงเส้นชนิดพิเศษ และในทิศทางตรงกันข้าม ป่าเชิงเส้นใดๆ ก็สามารถระบายสีขอบได้ 2 สี ดังนั้นสำหรับทุกGจึงสรุปได้ว่าla( G ) ≤ χ′( G ) ≤ 2 la( G ) ข้อสันนิษฐานของอากิยามะ ( ตั้งชื่อตามจิน อากิยามะ ) ระบุว่าซึ่งจะสรุปได้อย่างชัดเจนยิ่งขึ้นว่า2 la( G ) − 2 ≤ χ′( G ) ≤ 2 la( G )สำหรับกราฟที่มีดีกรีสูงสุดสามla( G )จะมีค่าเท่ากับสองเสมอ ดังนั้นในกรณีนี้ขอบเขตχ′( G ) ≤ 2 la( G )จะตรงกับขอบเขตที่กำหนดโดยทฤษฎีบทของ Vizing ^{[ 18 ]}${\displaystyle \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil }$

จำนวนThueของกราฟคือจำนวนสีที่จำเป็นในการระบายสีขอบซึ่งตรงตามข้อกำหนดที่เข้มงวดกว่านั้น คือ ในทุกเส้นทางที่มีความยาวเป็นเลขคู่ ครึ่งแรกและครึ่งหลังของเส้นทางจะต้องมีลำดับสีที่แตกต่างกัน

ความเป็นต้นไม้ของกราฟคือจำนวนสีขั้นต่ำที่จำเป็นเพื่อให้ขอบของแต่ละสีไม่มีวงจร (แทนที่จะเป็นปัญหาการระบายสีขอบแบบมาตรฐานที่ไม่มีคู่ขอบที่อยู่ติดกัน) กล่าวคือ เป็นจำนวนป่า ขั้นต่ำ ที่สามารถแบ่งขอบของกราฟออกเป็นได้^{[ 19 ]}แตกต่างจากดัชนีสี ความเป็นต้นไม้ของกราฟสามารถคำนวณได้ในเวลาพหุนาม^{[ 20 ]}

การระบายสีขอบด้วยรายการสีเป็นปัญหาที่กำหนดกราฟมาให้ โดยแต่ละขอบจะเชื่อมโยงกับรายการสี และต้องหาการระบายสีขอบที่เหมาะสม โดยที่สีของแต่ละขอบจะถูกดึงมาจากรายการสีของขอบนั้น ดัชนีสีรายการของกราฟGคือจำนวนที่เล็กที่สุดkที่มีคุณสมบัติว่า ไม่ว่าเราจะเลือกรายการสีสำหรับขอบอย่างไร ตราบใดที่แต่ละขอบมีสีอย่างน้อยkสีในรายการ การระบายสีก็จะทำได้แน่นอน ดังนั้น ดัชนีสีรายการจึงมีค่าอย่างน้อยเท่ากับดัชนีสีเสมอข้อสันนิษฐานของ Dinitzเกี่ยวกับการเติมเต็มตารางละติน บางส่วน อาจกล่าวใหม่ได้ว่า จำนวนสีรายการของขอบของกราฟสองส่วนสมบูรณ์K _n,nเท่ากับจำนวนสีขอบ  nของ มัน Galvin (1995)ได้แก้ข้อสันนิษฐานนี้โดยการพิสูจน์โดยทั่วไปว่าในทุกกราฟสองส่วน ดัชนีสีและดัชนีสีรายการมีค่าเท่ากัน มีการตั้งข้อสันนิษฐานว่าความเท่าเทียมกันระหว่างดัชนีสีและดัชนีสีรายการนั้นเป็นจริง แม้กระทั่งในกรณีทั่วไปสำหรับมัลติกราฟใดๆ ที่ไม่มีลูปในตัวเอง ข้อสันนิษฐานนี้ยังคงไม่มีข้อสรุป

รูปแบบการระบายสีจุดยอดที่ศึกษากันทั่วไปอื่นๆ อีกมากมายได้ถูกขยายไปสู่การระบายสีขอบด้วยเช่นกัน ตัวอย่างเช่น การระบายสีขอบแบบสมบูรณ์เป็นรูปแบบการระบายสีขอบของการระบายสีแบบสมบูรณ์ซึ่งเป็นการระบายสีขอบที่เหมาะสม โดยที่สีแต่ละคู่จะต้องแสดงด้วยขอบที่อยู่ติดกันอย่างน้อยหนึ่งคู่ และเป้าหมายคือการเพิ่มจำนวนสีทั้งหมดให้สูงสุด^{[ 21 ]}การระบายสีขอบแบบเข้มแข็งเป็นรูปแบบการระบายสีขอบของการระบายสีแบบเข้มแข็งซึ่งเป็นการระบายสีขอบที่ขอบสองเส้นทุกคู่ที่มีจุดปลายที่อยู่ติดกันจะต้องมีสีที่แตกต่างกัน^{[ 22 ]} การ ระบายสีขอบแบบเข้มแข็งมีการประยุกต์ใช้ในแผนการจัดสรรช่องสัญญาณสำหรับ เครือ ข่ายไร้สาย^{[ 23 ]}

การระบายสีขอบแบบไม่มีวงจรเป็นรูปแบบการระบายสีขอบแบบหนึ่งของการระบายสีแบบไม่มีวงจรซึ่งเป็นการระบายสีขอบที่คลาสสีสองคลาสใดๆ ก็ตามก่อให้เกิดกราฟย่อยแบบไม่มีวงจร (นั่นคือ ป่า) ^{[ 24 ]}ดัชนีสีแบบไม่มีวงจรของกราฟซึ่งแสดงด้วยคือจำนวนสีที่น้อยที่สุดที่จำเป็นเพื่อให้มีการระบายสีขอบแบบไม่มีวงจรที่เหมาะสมของ มีการคาดการณ์ว่าโดยที่คือดีกรีสูงสุดของ[ ^{25 ] ปัจจุบัน}ขอบเขตที่ดีที่สุดที่ทราบคือ[ ^{26 ] ปัญหา}จะง่ายขึ้นเมื่อมีเส้นรอบวง ขนาดใหญ่ โดยเฉพาะอย่างยิ่ง มีค่าคงที่เช่นนั้น ถ้าเส้นรอบวงของ มี ค่าอย่างน้อยแล้ว^{[ 27 ]}ผลลัพธ์ที่คล้ายกันคือ สำหรับทุกจะมีเช่นนั้น ถ้า มี ^{เส้นรอบวง}อย่างน้อยแล้ว^[ 28 ^]${\displaystyle G}$${\displaystyle a'(G)}$${\displaystyle G}$${\displaystyle a'(G)\leq \Delta +2}$${\displaystyle \Delta }$${\displaystyle G}$${\displaystyle a'(G)\leq \lceil 3.74(\Delta -1)\rceil }$${\displaystyle G}$${\displaystyle c}$${\displaystyle G}$${\displaystyle c\Delta \log \Delta }$${\displaystyle a'(G)\leq \Delta +2}$${\displaystyle \epsilon >0}$${\displaystyle g}$${\displaystyle G}$${\displaystyle g}$${\displaystyle a'(G)\leq (1+\epsilon )\Delta }$

เอปป์สไตน์ (2013)ศึกษาการระบายสีขอบ 3 เส้นของกราฟลูกบาศก์ที่มีคุณสมบัติเพิ่มเติมคือไม่มีวงจรสองสีใดที่ใช้ร่วมกันมากกว่าหนึ่งเส้น เขาแสดงให้เห็นว่าการมีอยู่ของการระบายสีดังกล่าวเทียบเท่ากับการมีอยู่ของภาพวาดของกราฟบนตารางจำนวนเต็มสามมิติ โดยมีขอบขนานกับแกนพิกัด และแต่ละเส้นขนานแกนมีจุดยอดไม่เกินสองจุด อย่างไรก็ตาม เช่นเดียวกับปัญหาการระบายสีขอบ 3 เส้นแบบมาตรฐาน การค้นหาการระบายสีประเภทนี้เป็นปัญหา NP-complete

การระบายสีแบบสมบูรณ์ (Total coloring)เป็นรูปแบบการระบายสีที่รวมการระบายสีจุดยอดและการระบายสีขอบเข้าด้วยกัน โดยกำหนดให้ทั้งจุดยอดและขอบต้องมีสีที่แตกต่างกัน คู่จุดยอดและขอบที่อยู่ติดกัน หรือขอบและขอบ จะต้องมีสีที่แตกต่างกัน เช่นเดียวกับจุดยอดสองจุดที่อยู่ติดกัน มีการคาดการณ์ (โดยการรวมทฤษฎีบทของ Vizing และทฤษฎีบทของ Brooks ) ว่ากราฟใดๆ ก็ตามมีการระบายสีแบบสมบูรณ์ที่จำนวนสีไม่เกินดีกรีสูงสุดบวกสอง แต่ข้อสันนิษฐานนี้ยังไม่ได้รับการพิสูจน์

ถ้ากราฟ 3-ปกติบนพื้นผิวถูกระบายสีขอบด้วย 3 สีกราฟคู่ ของมัน จะสร้างการแบ่งรูปสามเหลี่ยมบนพื้นผิวซึ่งถูกระบายสีขอบเช่นกัน (แม้โดยทั่วไปแล้วจะไม่ใช่การระบายสีขอบอย่างถูกต้อง) ในลักษณะที่ทุกสามเหลี่ยมมีขอบหนึ่งสีของแต่ละสี การระบายสีและการวางแนวอื่นๆ ของการแบ่งรูปสามเหลี่ยม พร้อมข้อจำกัดเฉพาะที่อื่นๆ เกี่ยวกับวิธีการจัดเรียงสีที่จุดยอดหรือหน้าของการแบ่งรูปสามเหลี่ยม อาจใช้เพื่อเข้ารหัสวัตถุทางเรขาคณิตหลายประเภท ตัวอย่างเช่น การแบ่งรูปสี่เหลี่ยมผืนผ้า (การแบ่งส่วนของการแบ่งรูปสี่เหลี่ยมผืนผ้าออกเป็นรูปสี่เหลี่ยมผืนผ้าขนาดเล็กกว่า โดยมีรูปสี่เหลี่ยมผืนผ้าสามรูปมาบรรจบกันที่ทุกจุดยอด) อาจอธิบายได้ในเชิงการจัดเรียงโดย "การติดป้ายแบบปกติ" ซึ่งเป็นการระบายสีขอบสองสีของการแบ่งรูปสามเหลี่ยมที่เป็นคู่ของการแบ่งส่วน โดยมีข้อจำกัดว่าขอบที่เชื่อมต่อกับแต่ละจุดยอดจะสร้างลำดับย่อยที่ต่อเนื่องกันสี่ลำดับ ซึ่งภายในแต่ละลำดับย่อยนั้นสีจะเหมือนกัน การติดป้ายนี้เป็นแบบคู่ขนานกับการระบายสีของการแบ่งย่อยสี่เหลี่ยมผืนผ้าเอง โดยที่ขอบแนวตั้งมีสีหนึ่ง และขอบแนวนอนมีอีกสีหนึ่ง ข้อจำกัดเฉพาะที่คล้ายคลึงกันเกี่ยวกับลำดับที่ขอบสีอาจปรากฏรอบจุดยอด อาจใช้เพื่อเข้ารหัสการฝังกริดเส้นตรงของกราฟระนาบและรูปทรงหลายเหลี่ยมสามมิติที่มีด้านขนานกับแกน สำหรับการติดป้ายแบบปกติทั้งสามประเภทนี้ ชุดของการติดป้ายแบบปกติของกราฟที่กำหนดไว้จะสร้างแลตทิซแบบกระจายที่สามารถใช้เพื่อแสดงรายการโครงสร้างทางเรขาคณิตทั้งหมดโดยอิงจากกราฟเดียวกันได้อย่างรวดเร็ว (เช่น รูปทรงหลายเหลี่ยมขนานกับแกนทั้งหมดที่มีโครงร่างเดียวกัน) หรือเพื่อค้นหาโครงสร้างที่ตรงตามข้อจำกัดเพิ่มเติม^{[ 29 ]}

ออโตมาตาจำกัดเชิงกำหนดอาจตีความได้ว่าเป็นกราฟทิศทางที่แต่ละจุดยอดมีดีกรีขาออกเท่ากันคือdและขอบของกราฟถูกระบายสีด้วยสี d ในลักษณะที่ว่าขอบสองเส้นใดๆ ที่มีจุดยอดต้นทางเดียวกันจะมีสีที่แตกต่างกันปัญหาการระบายสีถนนคือปัญหาการระบายสีขอบของกราฟทิศทางที่มีดีกรีขาออกสม่ำเสมอ ในลักษณะที่ออโตมาตาที่ได้จะมีคำประสานTrahtman (2009) ได้แก้ปัญหาการระบายสีถนนโดยพิสูจน์ว่าสามารถหาการระบายสีดังกล่าว ได้เมื่อใดก็ตามที่กราฟที่กำหนดเป็นกราฟที่เชื่อมต่อกันอย่างแน่นหนาและไม่ เป็นคาบ

ทฤษฎีบทของแรมซีย์เกี่ยวข้องกับปัญหา การ ระบายสีขอบของกราฟสมบูรณ์ ขนาดใหญ่ K _{n ด้วย} k สี เพื่อหลีกเลี่ยงการสร้างกราฟย่อยสมบูรณ์K _s ที่มีสีเดียว sที่กำหนด  ตามทฤษฎีบทนี้ มีจำนวนR _k ( s ) อยู่จำนวนหนึ่ง ซึ่งเมื่อใดก็ตามที่n ≥ R ( s )การระบายสีดังกล่าวเป็นไปไม่ได้ ตัวอย่างเช่นR ₂ (3) = 6นั่นคือ ถ้าขอบของกราฟK ₆ถูกระบายสีด้วย 2 สี จะมีสามเหลี่ยมที่มีสีเดียวเสมอ

เส้นทางในกราฟที่ระบายสีขอบเรียกว่า เส้นทาง สีรุ้งหากไม่มีสีซ้ำกันบนเส้นทางนั้น กราฟจะเรียกว่ากราฟสีรุ้ง หากมีเส้นทางสีรุ้งเชื่อมระหว่างจุดยอดสองคู่ใดๆ การระบายสีขอบของกราฟ G ด้วยสี 1...t เรียกว่าการระบายสีช่วง tหากใช้สีทั้งหมด และสีของขอบที่เชื่อมกับจุดยอดแต่ละจุดของ G นั้นแตกต่างกันและอยู่ในช่วงของจำนวนเต็ม

การระบายสีขอบของกราฟสมบูรณ์อาจใช้เพื่อกำหนดตารางการแข่งขันแบบรอบโรบินให้น้อยที่สุดเท่าที่จะเป็นไปได้ เพื่อให้ผู้แข่งขันแต่ละคู่ได้เล่นกันในรอบใดรอบหนึ่ง ในแอปพลิเคชันนี้ จุดยอดของกราฟจะสอดคล้องกับผู้แข่งขันในการแข่งขัน ขอบจะสอดคล้องกับเกม และสีของขอบจะสอดคล้องกับรอบที่เกมเหล่านั้นเล่น^{[ 30 ]}เทคนิคการระบายสีที่คล้ายกันนี้อาจใช้เพื่อกำหนดตารางการแข่งขันกีฬาประเภทอื่นที่ไม่ใช่แบบเล่นกันทั้งหมด ตัวอย่างเช่น ในลีกฟุตบอลแห่งชาติ (NFL ) คู่ของทีมที่จะเล่นกันในแต่ละปีจะถูกกำหนดโดยพิจารณาจากสถิติของทีมจากปีที่แล้ว จากนั้นจะใช้อัลกอริทึมการระบายสีขอบกับกราฟที่สร้างขึ้นจากชุดของการจับคู่เพื่อกำหนดเกมให้กับสุดสัปดาห์ที่เกมเหล่านั้นจะเล่น^{[ 31 ]}สำหรับแอปพลิเคชันนี้ ทฤษฎีบทของ Vizing บ่งชี้ว่าไม่ว่าชุดการจับคู่ใดจะถูกเลือก (ตราบใดที่ไม่มีทีมใดเล่นกันสองครั้งในฤดูกาลเดียวกัน) ก็สามารถหาตารางการแข่งขันที่ใช้สุดสัปดาห์มากกว่าจำนวนเกมต่อทีมได้ไม่เกินหนึ่งสุดสัปดาห์เสมอ

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

Gandham, Dawande และ Prakash (2005)ศึกษาปัญหาการจัดตารางเวลาการเชื่อมต่อ สำหรับ โปรโตคอลการสื่อสารเครือข่ายการเข้าถึงแบบหลายผู้ใช้แบบแบ่งเวลาบนเครือข่ายเซ็นเซอร์ในฐานะรูปแบบหนึ่งของการระบายสีขอบ ในปัญหานี้ จำเป็นต้องเลือกช่วงเวลาสำหรับขอบของเครือข่ายการสื่อสารไร้สายเพื่อให้แต่ละโหนดของเครือข่ายสามารถสื่อสารกับโหนดข้างเคียงแต่ละโหนดได้โดยไม่มีการรบกวน การใช้การระบายสีขอบแบบเข้มข้น (และใช้สองช่วงเวลาสำหรับแต่ละสีของขอบ หนึ่งช่วงเวลาสำหรับแต่ละทิศทาง) จะแก้ปัญหาได้ แต่อาจใช้ช่วงเวลามากกว่าที่จำเป็น ดังนั้น พวกเขาจึงมองหาการระบายสีกราฟแบบมีทิศทางที่เกิดจากการเพิ่มสีของขอบแบบไม่มีทิศทางของเครือข่ายเป็นสองเท่า โดยมีคุณสมบัติว่าขอบแบบมีทิศทางuv แต่ละเส้น มีสีที่แตกต่างจากขอบที่ออกจากvและจากเพื่อนบ้านของvพวกเขาเสนอฮิวริสติกสำหรับปัญหานี้โดยอิงจากอัลกอริทึมแบบกระจายสำหรับ การระบายสีขอบแบบ (Δ + 1)พร้อมกับขั้นตอนการประมวลผลภายหลังที่จัดตารางเวลาใหม่สำหรับขอบที่อาจรบกวนซึ่งกันและกัน

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

Jensen & Toft (1995)ระบุปัญหาที่ยังไม่ได้รับการแก้ไข 23 ข้อเกี่ยวกับการระบายสีขอบ ซึ่งรวมถึง:

• ข้อสันนิษฐานของโกลด์เบิร์ก (1973)ที่ว่าดัชนีสีและดัชนีเศษส่วนอยู่ภายในค่าเดียวกัน ซึ่งจะทำให้สามารถประมาณค่าดัชนีสีภายในสีเดียวได้ในเวลาพหุนาม
• มีข้อสันนิษฐานหลายประการของ Jakobsen และคนอื่นๆ เกี่ยวกับโครงสร้างของกราฟวิกฤตสำหรับการระบายสีขอบ ซึ่งเป็นกราฟระดับ 2 ที่กราฟย่อยใดๆ ก็ตามจะมีดีกรีสูงสุดน้อยกว่า หรือเป็นกราฟระดับ 1 เดิมที Jakobsen ตั้งข้อสันนิษฐานว่ากราฟวิกฤตทั้งหมดมีจำนวนจุดยอดเป็นเลขคี่ แต่ในที่สุดก็มีการพิสูจน์ว่าข้อสันนิษฐานนี้ไม่ถูกต้อง ข้อสันนิษฐานอื่นๆ อีกหลายข้อที่ทำให้ข้อสันนิษฐานนี้อ่อนลง หรือกำหนดขอบเขตจำนวนจุดยอดของกราฟวิกฤตและมัลติกราฟวิกฤต ยังคงเป็นสิ่งที่ยังไม่ได้รับการแก้ไข
• ปัญหาของวิซิงเกี่ยวกับการจำแนกระดับสูงสุดที่เป็นไปได้สำหรับกราฟระนาบคลาส 2
• ข้อสันนิษฐานเรื่องกราฟย่อยที่เต็มเกินของ AJW Hilton ซึ่งระบุว่ากราฟที่มีดีกรีอย่างน้อยn /3จะเป็นกราฟคลาส 1 หรือมีกราฟย่อยที่มีดีกรีΔเท่ากับกราฟดั้งเดิม และมีจำนวน จุดยอด kเป็นจำนวนคี่ โดยที่จำนวนขอบในกราฟย่อยนั้นมากกว่าΔ( k − 1)/2และข้อสันนิษฐานที่คล้ายกันโดยHerbert GrötzschและPaul Seymourเกี่ยวกับกราฟระนาบแทนที่จะเป็นกราฟดีกรีสูง
• ข้อสันนิษฐานของAmanda ChetwyndและAnthony Hilton (ซึ่งอาจย้อนกลับไปถึงงานของGabriel Andrew Dirac ก่อนหน้านี้ ) ที่ว่ากราฟปกติที่มีจำนวน จุดยอด nเป็นเลขคู่และมีดีกรีอย่างน้อยn /2จัดอยู่ในคลาส 1
• ข้อสันนิษฐานของClaude BergeและDR Fulkersonที่ว่า มัลติกราฟ 6-regular ที่เกิดจากการเพิ่มขอบทุกด้านของกราฟเชิงเดี่ยว 3-regular ที่ไม่มีสะพานเป็นสองเท่า อาจระบายสีขอบด้วยสีหกสีได้
• ข้อสันนิษฐานของฟิโอรินีและวิลสันที่ว่า กราฟระนาบ ที่ไม่มีรูปสามเหลี่ยม ทุก กราฟ ยกเว้นกราฟกรงเล็บK _1,3นั้น ไม่สามารถระบายสีขอบด้วย 3 สีได้อย่างเป็นเอกลักษณ์
• ข้อสันนิษฐานในปี 2012 ที่ว่า ถ้าGเป็นมัลติกราฟระนาบแบบd- ปกติ Gจะสามารถระบายสีขอบได้แบบ d ก็ต่อเมื่อ Gเชื่อมต่อขอบแบบคี่d ข้อสันนิษฐานนี้เป็นการวางนัยทั่วไปของ ทฤษฎีบทสี่สีซึ่งเกิดขึ้นที่d = 3 Maria Chudnovsky , Katherine Edwards และPaul Seymourพิสูจน์แล้วว่ามัลติกราฟระนาบแบบ 8-ปกติมีจำนวนสีขอบเท่ากับ 8 ^{[ 34 ]}