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

สำหรับเซตที่มีลำดับบางส่วนที่เข้มงวด ใดๆ ( S , <)กราฟเปรียบเทียบของ( S , <)คือกราฟ( S , ⊥)ซึ่งจุดยอดคือสมาชิกของSและขอบคือคู่{ u , v }ของสมาชิกที่u < vกล่าวคือ สำหรับเซตที่มีลำดับบางส่วน ให้ใช้กราฟแบบมีทิศทางที่ไม่มีวงจรใช้การปิดแบบส่งผ่านและลบทิศทางออก

ในทำนองเดียวกัน กราฟเปรียบเทียบคือกราฟที่มี ทิศทาง แบบถ่ายทอด^{[ 3 ]}การกำหนดทิศทางให้กับขอบของกราฟ (กล่าวคือทิศทางของกราฟ) โดยที่ความสัมพันธ์ประชิดของกราฟทิศทาง ที่ได้นั้น เป็นแบบถ่ายทอด กล่าวคือ เมื่อใดก็ตามที่มีขอบทิศทาง( x , y )และ( y , z )จะต้องมีขอบ( x , z ) อยู่ ด้วย

เราสามารถแสดงลำดับบางส่วนจำกัดใดๆ ก็ได้ในรูปของตระกูลเซต โดยที่x < yในลำดับบางส่วนเมื่อใดก็ตามที่เซตที่สอดคล้องกับxเป็นเซตย่อยของเซตที่สอดคล้องกับyด้วยวิธีนี้ กราฟเปรียบเทียบสามารถแสดงให้เห็นว่าเทียบเท่ากับกราฟบรรจุของตระกูลเซต กล่าวคือ กราฟที่มีจุดยอดสำหรับแต่ละเซตในตระกูลและขอบระหว่างสองเซตเมื่อใดก็ตามที่เซตหนึ่งเป็นเซตย่อยของอีกเซตหนึ่ง^{[ 4 ]} หรืออีกทางหนึ่ง เราสามารถแสดงลำดับบางส่วนด้วยตระกูลของจำนวนเต็มโดยที่x < yเมื่อใดก็ตามที่จำนวนเต็มที่สอดคล้องกับxเป็นตัวหารของจำนวนเต็มที่สอดคล้องกับyเนื่องจากโครงสร้างนี้ กราฟเปรียบเทียบจึงถูกเรียกว่ากราฟตัวหารด้วย^{[ 2 ]}

กราฟเปรียบเทียบสามารถระบุลักษณะได้ว่าเป็นกราฟที่สำหรับวัฏจักรทั่วไปทุกวัฏจักร (ดูด้านล่าง) ที่มีความยาวเป็นเลขคี่ จะสามารถหาขอบ( x , y )ที่เชื่อมต่อจุดยอดสองจุดที่มีระยะห่างสองในวัฏจักรได้ ขอบดังกล่าวเรียกว่าคอร์ดสามเหลี่ยมในบริบทนี้ วัฏจักรทั่วไปถูกกำหนดให้เป็นการเดินแบบปิดที่ใช้ขอบแต่ละขอบของกราฟไม่เกินหนึ่งครั้งในแต่ละทิศทาง^{[ 5 ]}กราฟเปรียบเทียบยังสามารถระบุลักษณะได้ด้วยรายการของ กราฟ ย่อยที่เหนี่ยวนำที่ต้องห้าม^{[ 6 ]}

กราฟโคคอมพาริ เบชัน (Cocomparability graph ) คือกราฟส่วนเติมเต็มของกราฟคอมพาริเบชัน (Comparability graph) กล่าวคือ เมื่อกำหนดกราฟ คอมพาริเบชัน G = ( V , E )แล้ว กราฟโคคอมพาริ เบชัน G̅ = ( V , E̅ )จะมีเซตของจุดยอดเดียวกัน แต่มีเซตของขอบที่เป็นส่วนเติมเต็ม กล่าวคือ จุดยอดสองจุดจะอยู่ติดกันในG̅ก็ต่อเมื่อจุดยอดทั้งสองนั้นไม่อยู่ติดกันในG

กราฟโคคอมแพริบิลิตี้คือกราฟจุดตัดของเส้นโค้งต่อเนื่องระหว่างเส้นขนานสองเส้น หรือเทียบเท่ากับกราฟจุดตัดของช่วงบนเส้นขนานสองเส้น^{[ 7 ]}กราฟจะเป็นกราฟโคคอมแพริบิลิตี้ก็ต่อเมื่อส่วนเติมเต็มของกราฟนั้นยอมรับการวางแนวแบบทรานซิทีฟ

กราฟ Cocomparability ก่อให้เกิดคลาสย่อยที่สำคัญของกราฟสมบูรณ์โดยสืบทอดคุณสมบัตินี้มาจากข้อเท็จจริงที่ว่าทั้งกราฟเปรียบเทียบและส่วนเติมเต็มของกราฟเหล่านั้นเป็นกราฟสมบูรณ์ (ตามทฤษฎีบทของ Dilworthและทฤษฎีบทของ Mirskyตามลำดับ) ^{[ 8 ]}

กราฟความเปรียบเทียบร่วมทุกกราฟปราศจากสามเท่าของดาวเคราะห์น้อย (AT-free) ^{[ 9 ]}ซึ่งทำให้กราฟเหล่านี้อยู่ในลำดับชั้น: ช่วง ⊂ สี่เหลี่ยมคางหมู ⊂ ความเปรียบเทียบร่วม ⊂ ปราศจาก ATและ การเรียงสับเปลี่ยน ⊂ สี่เหลี่ยมคางหมู ⊂ ความเปรียบเทียบร่วม ⊂ ปราศจากAT

กลุ่มของกราฟความเท่าเทียมกันนั้นเป็นกลุ่มที่เติมเต็มตัวเองได้ กล่าวคือ ส่วนเติมเต็มของกราฟความเท่าเทียมกันคือกราฟความเท่าเทียมกัน และในทางกลับกัน

กราฟช่วงเป็นกราฟที่คอร์ดัลและมีส่วนประกอบที่เปรียบเทียบได้ กล่าวคือส่วนประกอบของกราฟช่วง ใดๆ ก็ คือกราฟเปรียบเทียบ และความสัมพันธ์ของการเปรียบเทียบเรียกว่าลำดับช่วง^{[ 10 ]}

กราฟความเทียบเคียงกันเป็นคลาสย่อยของกราฟสตริงส่วนเติมเต็มของกราฟความเทียบเคียงกันทุกกราฟคือกราฟสตริง^{[ 11 ]}

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

กราฟการเรียงสับเปลี่ยนคือกราฟการบรรจุบนเซตของช่วงเวลา^{[ 12 ]}ดังนั้น กราฟการเรียงสับเปลี่ยนจึงเป็นคลาสย่อยอีกคลาสหนึ่งของกราฟการเปรียบเทียบ

กราฟที่สมบูรณ์แบบอย่างไม่สำคัญคือกราฟเปรียบเทียบของต้นไม้ที่มีราก [ ^{13 ] โค}กราฟสามารถกำหนดลักษณะได้ว่าเป็นกราฟเปรียบเทียบของลำดับบางส่วนแบบอนุกรมขนานดังนั้น โคกราฟจึงเป็นกราฟเปรียบเทียบด้วย^{[ 14 ]}

กราฟเกณฑ์เป็นกราฟเปรียบเทียบชนิดพิเศษอีกแบบหนึ่ง

กราฟเปรียบเทียบทุกกราฟเป็น กราฟ ที่สมบูรณ์แบบ ความสมบูรณ์แบบของกราฟเปรียบเทียบคือทฤษฎีบทของ Mirskyและความสมบูรณ์แบบของกราฟส่วนเติมเต็มคือทฤษฎีบทของ Dilworthข้อเท็จจริงเหล่านี้ร่วมกับทฤษฎีบทกราฟที่สมบูรณ์แบบสามารถใช้พิสูจน์ทฤษฎีบทของ Dilworth จากทฤษฎีบทของ Mirsky หรือในทางกลับกันได้^{[ 15 ]}โดยเฉพาะอย่างยิ่ง กราฟเปรียบเทียบเป็นกราฟที่เรียงลำดับได้อย่างสมบูรณ์แบบ ซึ่งเป็นคลาสย่อยของกราฟที่สมบูรณ์แบบ: อัลกอริทึม การระบายสีแบบโลภสำหรับการเรียงลำดับเชิงโทโพโลยีของการวางแนวแบบทรานซิทีฟของกราฟจะระบายสีกราฟเหล่านั้นอย่างเหมาะสมที่สุด^{[ 16 ]}

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

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

• กราฟขอบเขตคือ กราฟที่แตกต่างออกไปซึ่งกำหนดจากลำดับบางส่วน