ในทฤษฎีกราฟ กราฟเกณฑ์(threshold graph)คือกราฟที่สามารถสร้างขึ้นจากกราฟที่มีจุดยอดเดียวได้โดยการประยุกต์ใช้การดำเนินการสองอย่างต่อไปนี้ซ้ำๆ:

1. การเพิ่มจุดยอดเดี่ยวที่แยกออกมาลงในกราฟ
2. การเพิ่มจุดยอดเด่น เพียงจุดเดียวลง ในกราฟ กล่าวคือ จุดยอดเดียวที่เชื่อมต่อกับจุดยอดอื่นๆ ทั้งหมด

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

กราฟเกณฑ์ (Threshold graphs) ถูกนำเสนอครั้งแรกโดยChvátal & Hammer (1977)บทหนึ่งเกี่ยวกับกราฟเกณฑ์ปรากฏอยู่ในGolumbic (1980)และหนังสือของMahadev & Peled (1995)ก็เป็นหนังสือที่กล่าวถึงกราฟ เกณฑ์โดยเฉพาะ

นิยามที่เทียบเท่ากันคือดังต่อไปนี้: กราฟเป็นกราฟเกณฑ์ (threshold graph) ถ้ามีจำนวนจริงและสำหรับแต่ละจุดยอดมีน้ำหนักจุดยอดที่เป็นจำนวนจริงโดยที่สำหรับจุดยอดสองจุดใดๆจะเป็นขอบก็ต่อเมื่อ ${\displaystyle S}$${\displaystyle v}$${\displaystyle w(v)}$${\displaystyle v,u}$${\displaystyle uv}$${\displaystyle w(u)+w(v)>S}$

นิยามที่เทียบเท่ากันอีกอย่างหนึ่งคือ: กราฟเป็นกราฟเกณฑ์ ถ้ามีจำนวนจริงและสำหรับแต่ละจุดยอดมีน้ำหนักจุดยอดที่เป็นจำนวนจริงโดยที่สำหรับเซตจุดยอดใดๆจะเป็นอิสระก็ต่อเมื่อ${\displaystyle T}$${\displaystyle v}$${\displaystyle a(v)}$${\displaystyle X\subseteq V}$${\displaystyle X}$${\displaystyle \sum _{v\in X}a(v)\leq T.}$

ชื่อ "กราฟเกณฑ์" มาจากคำจำกัดความเหล่านี้: Sคือ "เกณฑ์" สำหรับคุณสมบัติของการเป็นขอบ หรือในทำนองเดียวกันTคือเกณฑ์สำหรับการเป็นอิสระต่อกัน

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

จากนิยามที่ใช้การบวกจุดยอดซ้ำๆ เราสามารถอนุมานวิธีการอื่นในการอธิบายกราฟเกณฑ์ได้อย่างเฉพาะเจาะจง โดยใช้สตริงของสัญลักษณ์จะเป็นอักขระตัวแรกของสตริงเสมอ และแทนจุดยอดแรกของกราฟ อักขระถัดไปแต่ละตัวจะเป็นซึ่งหมายถึงการบวกจุดยอดเดี่ยว (หรือ จุดยอด รวม ) หรือซึ่งหมายถึงการบวกจุดยอดเด่น (หรือ จุดยอด เชื่อม ) ตัวอย่างเช่น สตริงแทนกราฟรูปดาวที่มีใบสามใบ ในขณะที่แทนเส้นทางบนจุดยอดสามจุด กราฟในรูปสามารถแสดงได้ดังนี้${\displaystyle \epsilon }$${\displaystyle u}$${\displaystyle j}$${\displaystyle \epsilon uuj}$${\displaystyle \epsilon uj}$${\displaystyle \epsilon uuujuuj}$

กราฟเกณฑ์ (Threshold graph) เป็นกรณีพิเศษของโคกราฟ (Cograph)สปลิตกราฟ (Split graph)และกราฟสมบูรณ์แบบโดยปริยาย (Trivially perfect graph) กราฟจะเป็นกราฟเกณฑ์ก็ต่อเมื่อเป็นทั้งโคกราฟและสปลิตกราฟ ทุกกราฟที่เป็นทั้งกราฟสมบูรณ์แบบโดยปริยายและกราฟส่วนเติมเต็มของกราฟสมบูรณ์แบบโดยปริยายจะเป็นกราฟเกณฑ์ กราฟเกณฑ์ยังเป็นกรณีพิเศษของกราฟช่วง (Interval graph ) ความสัมพันธ์ทั้งหมดเหล่านี้สามารถอธิบายได้ในแง่ของลักษณะเฉพาะโดยกราฟย่อยเหนี่ยวนำที่ต้องห้าม โคกราฟคือกราฟที่ไม่มีเส้นทางเหนี่ยวนำบนจุดยอดสี่จุด P₄ _และกราฟเกณฑ์คือกราฟที่ไม่มี P₄, C₄ หรือ 2K₂ เหนี่ยวนำ_C₄คือ_{วัฏจักร}ของ_จุดยอดสี่จุดและ 2K₂ _{คือ ส่วนเติมเต็มของมัน นั่นคือขอบสอง ขอบ}ที่ไม่ทับซ้อนกัน นี่จึงอธิบายได้ว่าทำไมกราฟเกณฑ์จึงปิดภายใต้การรับส่วนเติมเต็ม กราฟ P ₄นั้นเป็นกราฟที่เติมเต็มตัวเองได้ ดังนั้นหากกราฟใดปราศจาก P ₄ , C ₄และ 2K ₂กราฟส่วนเติมเต็มของมันก็ปราศจาก P 4 เช่นกัน

Heggernes & Kratsch (2007)แสดงให้เห็นว่ากราฟเกณฑ์สามารถรับรู้ได้ในเวลาเชิงเส้น หากกราฟไม่ใช่กราฟเกณฑ์จะมีการส่งออก สิ่งกีดขวาง (หนึ่งใน P ₄ , C ₄หรือ 2K _{2 )}

• กราฟความไม่แตกต่าง
• กราฟอนุกรม-ขนาน
• ไฮเปอร์กราฟเกณฑ์^{[ 1 ]}

• กราฟเกณฑ์ , ระบบสารสนเทศเกี่ยวกับคลาสกราฟและส่วนประกอบต่างๆ