ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟที่ปราศจากสามเหลี่ยมคือ กราฟแบบไม่มีทิศทางที่ไม่มีจุดยอดสามจุดใด ๆ ประกอบกันเป็นรูปสามเหลี่ยมของเส้นขอบ กราฟที่ปราศจากสามเหลี่ยมอาจนิยามได้อีกอย่างว่า กราฟที่มีจำนวนคลิก  ≤ 2 กราฟที่มีเส้นรอบวง  ≥ 4 กราฟที่ไม่มีวัฏจักร 3 วงเหนี่ยวนำหรือกราฟ ที่เป็นอิสระเฉพาะที่

ตามทฤษฎีบทของ Turánกราฟ ที่ไม่มีรูปสามเหลี่ยมที่มีจุดยอด nจุดและมีจำนวนขอบมากที่สุดจะเป็นกราฟสองส่วนสมบูรณ์ซึ่งจำนวนจุดยอดในแต่ละด้านของการแบ่งสองส่วนนั้นเท่ากันมากที่สุดเท่าที่จะเป็นไปได้

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

เป็นไปได้ที่จะทดสอบว่ากราฟที่มีขอบปราศจากสามเหลี่ยมหรือไม่ในเวลา^{ที่ซ่อนปัจจัยย่อยพหุนาม นี่คือเลขชี้กำลังของการคูณเมทริกซ์อย่างรวดเร็ว [} 1 ] ซึ่งสรุปได้^{ว่าการ}ตรวจจับสามเหลี่ยมสามารถแก้ไขได้ในเวลาอีกวิธีหนึ่งคือการหาร่องรอยของA ³โดยที่Aคือเมทริกซ์ประชิดของกราฟ ร่องรอยจะเป็นศูนย์ก็ต่อเมื่อกราฟปราศจากสามเหลี่ยม สำหรับกราฟหนาแน่นการใช้อัลกอริธึมง่ายๆ นี้ซึ่งอาศัยการคูณเมทริกซ์อีกครั้งจะมีประสิทธิภาพมากกว่า เนื่องจากทำให้ความซับซ้อนของเวลาลดลงเหลือโดยที่คือจำนวนจุดยอด ${\displaystyle m}$${\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}}$${\displaystyle {\tilde {O}}}$${\displaystyle \omega }$${\displaystyle \omega <2.372}$${\displaystyle O(m^{1.407})}$${\displaystyle O(n^{\โอเมก้า })}$${\displaystyle n}$

แม้ว่าจะมีการค้นพบอัลกอริธึมการคูณเมทริกซ์ที่มีเวลา แต่ขอบเขตเวลาที่ดีที่สุดที่คาดหวังได้จากแนวทางเหล่านี้คือหรือในความซับซ้อนแบบละเอียดสมมติฐานสามเหลี่ยมแบบเบาบางเป็นสมมติฐานความยากในการคำนวณ ที่ยังไม่ได้รับการพิสูจน์ ซึ่งยืนยันว่าไม่มีขอบเขตเวลาในรูปแบบที่เป็นไปได้สำหรับค่าใดๆโดยไม่คำนึงถึงเทคนิคอัลกอริธึมที่ใช้ สมมติฐานนี้และสมมติฐานสามเหลี่ยมแบบหนาแน่น ที่สอดคล้องกัน ซึ่งยืนยันว่าไม่มีขอบเขตเวลาในรูปแบบ ที่เป็นไปได้ บ่งบอกถึงขอบเขตล่างสำหรับปัญหาการคำนวณอื่นๆ อีกหลายปัญหาในการเพิ่มประสิทธิภาพเชิงรวมและเรขาคณิตเชิงคำนวณ^{[ 2 ]}${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3})}$${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3-\delta })}$${\displaystyle \delta >0}$${\displaystyle O(n^{\โอเมก้า -\delta })}$

ดังที่Imrich, Klavžar & Mulder (1999)ได้แสดงให้เห็น การรู้จำกราฟแบบไม่มีสามเหลี่ยมมีความซับซ้อนเทียบเท่ากับ การรู้จำ กราฟแบบมัธยฐานอย่างไรก็ตาม อัลกอริทึมที่ดีที่สุดในปัจจุบันสำหรับการรู้จำกราฟแบบมัธยฐานใช้การตรวจจับสามเหลี่ยมเป็นขั้นตอนย่อยแทนที่จะเป็นในทางกลับกัน

ความซับซ้อนของต้นไม้ตัดสินใจหรือความซับซ้อนของการสอบถามของปัญหา โดยที่การสอบถามไปยังออราเคิลซึ่งจัดเก็บเมทริกซ์ความประชิดของกราฟ คือΘ( n ² )อย่างไรก็ตาม สำหรับอัลกอริธึมควอนตัม^ขอบล่างที่ทราบดีที่สุดคือΩ( n )แต่อัลกอริธึมที่ทราบดีที่สุดคือO ( n ^5/4 ) [ ^{3 ]}

เซตอิสระของจุดยอด (โดยที่คือฟังก์ชันพื้น ) ใน กราฟไร้สามเหลี่ยมที่มี nจุดยอดนั้นหาได้ง่าย: ต้องมีจุดยอดที่มีเพื่อนบ้านอย่างน้อย (ในกรณีนี้ เพื่อนบ้านเหล่านั้นเป็นเซตอิสระ) หรือจุดยอดทั้งหมดมีเพื่อนบ้านน้อยกว่า(ในกรณีนี้เซตอิสระสูงสุด ใดๆ ต้องมีจุดยอดอย่างน้อย) ^{[ 4 ]}ขอบเขตนี้สามารถกระชับขึ้นได้เล็กน้อย: ในทุกกราฟไร้สามเหลี่ยมจะมีเซตอิสระของจุดยอด และในบางกราฟไร้สามเหลี่ยม เซตอิสระทุกเซตจะมีจุดยอด^{[ 5 ]}วิธีหนึ่งในการสร้างกราฟไร้สามเหลี่ยมที่เซตอิสระทั้งหมดมีขนาดเล็กคือกระบวนการไร้สามเหลี่ยม^{[ 6 ]}ซึ่งสร้างกราฟไร้สามเหลี่ยมสูงสุดโดยการเพิ่มขอบที่เลือกแบบสุ่มซ้ำๆ ซึ่งไม่ทำให้เกิดสามเหลี่ยมด้วยความน่าจะเป็นสูงกระบวนการนี้จะสร้างกราฟที่มีจำนวนอิสระนอกจากนี้ยังสามารถหากราฟปกติที่มีคุณสมบัติเดียวกันได้^{[ 7 ]}${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor \cdot \rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \Omega ({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$

ผลลัพธ์เหล่านี้อาจตีความได้ว่าเป็นการให้ขอบเขตเชิงอะซิมโทติกของจำนวนแรมซีย์ R(3, t ) ในรูปแบบ: ถ้าขอบของกราฟสมบูรณ์บนจุดยอดถูกระบายสีแดงและสีน้ำเงิน แสดงว่ากราฟสีแดงนั้นมีรูปสามเหลี่ยม หรือถ้าไม่มีรูปสามเหลี่ยม ก็จะต้องมีเซตอิสระขนาดtที่สอดคล้องกับคลิกขนาดเดียวกันในกราฟสีน้ำเงิน ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$

งานวิจัยจำนวนมากเกี่ยวกับกราฟที่ไม่มีสามเหลี่ยมมุ่งเน้นไปที่การระบายสีกราฟ กราฟ สองส่วน ทุกกราฟ (นั่นคือ กราฟที่สามารถระบายสีได้ 2 สี) เป็นกราฟที่ไม่มีสามเหลี่ยม และทฤษฎีบทของ Grötzsch ระบุว่า กราฟระนาบที่ไม่มีสามเหลี่ยมทุก กราฟ สามารถระบายสีได้ 3 สี^{[ 8 ]}อย่างไรก็ตาม กราฟที่ไม่มีสามเหลี่ยมที่ไม่ใช่ระนาบอาจต้องใช้สีมากกว่าสามสี

การสร้างกราฟที่ไม่มีสามเหลี่ยมที่มีจำนวนสีสูงตามอำเภอใจเป็นครั้งแรกนั้นมาจากTutte (เขียนในนามBlanche Descartes ^{[ 9 ]} ) การสร้างนี้เริ่มต้นจากกราฟที่มีจุดยอดเดียว เช่นและสร้างแบบอุปนัยดังนี้: ให้มีจุดยอด จากนั้นเลือกเซตของจุดยอด และสำหรับแต่ละเซตย่อยของที่มีขนาดให้เพิ่มสำเนาที่ไม่ซ้ำกันของและเชื่อมเข้ากับด้วยการจับคู่ จากหลักการรังนกพิราบ จะได้แบบอุปนัยว่าไม่สามารถระบายสีได้ เนื่องจากอย่างน้อยหนึ่งในเซตจะต้องถูกระบายสีแบบโมโนโครมาติก หากเราได้รับอนุญาตให้ใช้สีเพียง k สีMycielski (1955)ได้กำหนดการสร้าง ซึ่งปัจจุบันเรียกว่าMycielskianสำหรับการสร้างกราฟที่ไม่มีสามเหลี่ยมใหม่จากกราฟที่ไม่มีสามเหลี่ยมอีกกราฟหนึ่ง หากกราฟมีจำนวนสีk Mycielskian ของกราฟนั้นจะมีจำนวนสีk  + 1 ดังนั้นการสร้างนี้จึงสามารถใช้เพื่อแสดงว่าอาจต้องใช้สีจำนวนมากตามอำเภอใจในการระบายสีกราฟที่ไม่มีสามเหลี่ยมที่ไม่ใช่ระนาบ โดยเฉพาะอย่างยิ่งกราฟ Grötzschซึ่งเป็นกราฟ 11 จุดยอดที่เกิดจากการประยุกต์ใช้การสร้างของ Mycielski ซ้ำๆ เป็นกราฟที่ไม่มีสามเหลี่ยมซึ่งไม่สามารถระบายสีด้วยสีน้อยกว่าสี่สีได้ และเป็นกราฟที่เล็กที่สุดที่มีคุณสมบัตินี้^{[ 10 ]} Gimbel & Thomassen (2000)และNilli (2000)แสดงให้เห็นว่าจำนวนสีที่จำเป็นในการระบายสีกราฟที่ไม่มีสามเหลี่ยมที่มีขอบ m ใดๆ คือ${\displaystyle G_{1}}$${\displaystyle G_{k+1}}$${\displaystyle G_{k}}$${\displaystyle G_{k}}$${\displaystyle n}$${\displaystyle Y}$${\displaystyle k(n-1)+1}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle n}$${\displaystyle G_{k}}$${\displaystyle X}$${\displaystyle G_{k+1}}$${\displaystyle k}$${\displaystyle X}$

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

และมีกราฟที่ไม่มีรูปสามเหลี่ยมซึ่งมีจำนวนสีที่แปรผันตามขอบเขตนี้

นอกจากนี้ ยังมีผลลัพธ์หลายอย่างที่เชื่อมโยงการระบายสีกับดีกรีต่ำสุดในกราฟที่ไม่มีสามเหลี่ยมAndrásfai, Erdős & Sós (1974)พิสูจน์ว่ากราฟที่ไม่มีสามเหลี่ยมที่ มี nจุดยอด ซึ่งแต่ละจุดยอดมีเพื่อนบ้านมากกว่า 2n / 5 จะต้องเป็นกราฟสองส่วน นี่คือผลลัพธ์ที่ดีที่สุดเท่าที่จะเป็นไปได้ในประเภทนี้ เนื่องจากวัฏจักร 5 ต้องการสามสี แต่มีเพื่อนบ้าน 2n/5 ต่อจุดยอดพอดีด้วยแรงบันดาลใจจากผลลัพธ์นี้Erdős & Simonovits (1973)ตั้งข้อสันนิษฐานว่า กราฟที่ไม่มีสามเหลี่ยมที่มี nจุดยอด ซึ่งแต่ละจุดยอดมีเพื่อนบ้านอย่างน้อยn /3 สามารถระบายสีได้ด้วยสีเพียงสามสีเท่านั้น อย่างไรก็ตามHäggkvist (1981)ได้หักล้างข้อสันนิษฐานนี้โดยการค้นพบตัวอย่างค้านที่แต่ละจุดยอดของกราฟ Grötzsch ถูกแทนที่ด้วยเซตอิสระที่มีขนาดที่เลือกอย่างระมัดระวังJin (1995)แสดงให้เห็นว่า กราฟไร้สามเหลี่ยมที่มี nจุดยอดใดๆ ที่แต่ละจุดยอดมีเพื่อนบ้านมากกว่า 10 n /29 จะต้องสามารถระบายสีได้ 3 สี นี่เป็นผลลัพธ์ที่ดีที่สุดที่เป็นไปได้ในประเภทนี้ เนื่องจากกราฟของ Häggkvist ต้องการสี่สีและมีเพื่อนบ้าน 10 n /29 ต่อจุดยอดพอดี ในที่สุด Brandt & Thomassé (2006)พิสูจน์ว่า กราฟไร้สามเหลี่ยมที่มี nจุดยอดใดๆ ที่แต่ละจุดยอดมีเพื่อนบ้านมากกว่าn /3 จะต้องสามารถระบายสีได้ 4 สี ผลลัพธ์เพิ่มเติมในประเภทนี้เป็นไปไม่ได้ เนื่องจาก Hajnal ^{[ 11 ]}พบตัวอย่างของกราฟไร้สามเหลี่ยมที่มีจำนวนสีมากตามอำเภอใจและดีกรีต่ำสุด (1/3 − ε) nสำหรับ ε > 0 ใดๆ

• กราฟ Andrásfaiคือตระกูลของกราฟวงกลมที่ไม่มีรูปสามเหลี่ยมและมีเส้นผ่านศูนย์กลางสอง
• กราฟเฮนสัน (Henson graph ) คือกราฟอนันต์ที่ปราศจากสามเหลี่ยม ซึ่งประกอบด้วยกราฟจำกัดที่ปราศจากสามเหลี่ยมทั้งหมดเป็นกราฟย่อยที่เกิดจากการเหนี่ยวนำ
• กราฟเลื่อน (Shift graph ) คือตระกูลของกราฟที่ไม่มีรูปสามเหลี่ยมและมีจำนวนสีสูงมากตามอำเภอใจ
• กราฟKneser ไม่มีรูปสามเหลี่ยมและมีจำนวนสีตามโครมาติก${\displaystyle KG_{3k-1,k}}$${\displaystyle k+1}$
• ปัญหา สามเหลี่ยมสีเดียวคือ ปัญหาการแบ่งขอบของกราฟที่กำหนดให้เป็นกราฟสองกราฟที่ไม่มีสามเหลี่ยม
• ปัญหา Ruzsa–Szemerédiบนกราฟที่ขอบทุกเส้นเป็นส่วนหนึ่งของสามเหลี่ยมเพียงรูปเดียวเท่านั้น

• "Graphclass: ปราศจากสามเหลี่ยม"ระบบสารสนเทศเกี่ยวกับคลาสของกราฟและส่วนประกอบต่างๆ