ในสาขาคณิตศาสตร์ทฤษฎีกราฟกราฟChvátalเป็นกราฟแบบไม่มีทิศทางที่มี 12 จุดยอดและ 24 ขอบ ซึ่งค้นพบโดยVáclav Chvátalในปี 1970 เป็นกราฟที่เล็กที่สุดที่ไม่มีรูปสามเหลี่ยมเป็น กราฟ ปกติ 4 จุดและมีสี 4สี

กราฟ Chvátal ไม่มีรูปสามเหลี่ยม : เส้นรอบวง (ความยาวของวงจรที่สั้นที่สุด) คือสี่ เป็นกราฟปกติ 4 : แต่ละจุดยอดมีเพื่อนบ้านสี่จุดพอดีจำนวนสี ของมัน คือ 4: สามารถระบายสีได้โดยใช้สี่สี แต่ไม่สามารถระบายสีได้โดยใช้เพียงสามสี ดังที่ Chvátal สังเกต กราฟนี้เป็นกราฟที่ไม่มีรูปสามเหลี่ยมที่มีจำนวนสี 4 และเป็นกราฟปกติ 4 ที่เล็กที่สุดที่เป็นไปได้ กราฟที่ไม่มีรูปสามเหลี่ยมที่มีจำนวนสี 4 ที่เล็กกว่าคือกราฟGrötzschซึ่งมี 11 จุดยอด แต่มีดีกรีสูงสุด 5 และไม่ใช่กราฟปกติ^{[ 1 ]}

ตามทฤษฎีบทของบรู๊คส์ทุกๆ${\displaystyle k}$-กราฟปกติ (ยกเว้นวัฏจักรคี่และคลิก) มีจำนวนสีไม่เกิน${\displaystyle k}$นอกจากนี้ เป็นที่ทราบกันมาตั้งแต่สมัยErdős (1959)แล้วว่า สำหรับทุกๆ${\displaystyle k\geq 3}$และ${\displaystyle \ell \geq 3}$มีอยู่${\displaystyle k}$กราฟสีที่มีเส้นรอบวง${\displaystyle \ell }$[ ^{2 ]}ในส่วนที่เกี่ยวข้องกับผลลัพธ์ทั้งสองนี้และตัวอย่างหลายตัวอย่างรวมถึงกราฟ Chvátal นั้น^Branko Grünbaumตั้งข้อสันนิษฐานว่าสำหรับทุกๆ${\displaystyle k}$และ${\displaystyle \ell }$มีอยู่${\displaystyle k}$-โครมาติก${\displaystyle k}$-กราฟปกติที่มีเส้นรอบวง${\displaystyle \ell }$[ ^{3 ]}กราฟ Chvátal แก้ปัญหากรณี^นี้${\displaystyle k=\ell =4}$ของสมมติฐานนี้^{[ 1 ]}สมมติฐานของ Grünbaum ถูกหักล้างสำหรับค่าที่ใหญ่พอสมควร${\displaystyle k}$โดยโยฮันเซน ผู้ซึ่งแสดงให้เห็นว่าจำนวนสีของกราฟที่ไม่มีรูปสามเหลี่ยมคือ${\displaystyle O(\Delta /\log \Delta )}$ที่ไหน${\displaystyle \Delta }$คือระดับสูงสุดของจุดยอดและ${\displaystyle O}$แนะนำ สัญกร ณ์O ขนาดใหญ่^{[ 4 ]}อย่างไรก็ตาม แม้จะมีการพิสูจน์หักล้างนี้แล้ว การค้นหาตัวอย่างเช่นกราฟ Chvátal ที่มีเส้นรอบวงสูงก็ยังคงน่าสนใจอยู่${\displaystyle k}$-โครมาติก${\displaystyle k}$กราฟปกติสำหรับค่าเล็กๆ ของ${\displaystyle k}$.

ข้อสันนิษฐานทางเลือกอีกประการหนึ่งของบรูซ รีดกล่าวว่า กราฟที่ไม่มีรูปสามเหลี่ยมที่มีดีกรีสูงจะต้องมีจำนวนสีที่น้อยกว่าดีกรีของมันอย่างมาก และโดยทั่วไปแล้ว กราฟที่มีดีกรีสูงสุดจะต้องมีจำนวนสีที่น้อยกว่าดีกรีของมันมาก${\displaystyle \Delta }$และขนาดกลุ่มสูงสุด${\displaystyle \omega }$ต้องมีเลขสี^{[ 4 ]}$${\displaystyle \chi (G)\leq \left\lceil {\frac {\Delta +\omega +1}{2}}\right\rceil .}$$ คดี${\displaystyle \omega =2}$จากข้อสันนิษฐานนี้ จะเกิดขึ้นได้ก็ต่อเมื่อมีค่ามากพอ${\displaystyle \Delta }$จากผลลัพธ์ของ Johanssen กราฟ Chvátal แสดงให้เห็นว่าการปัดเศษขึ้นในสมมติฐานของ Reed นั้นจำเป็น เพราะสำหรับกราฟ Chvátal นั้น${\displaystyle (\เดลต้า +\โอเมก้า +1)/2=7/2}$ตัวเลขที่น้อยกว่าจำนวนสี แต่เมื่อปัดขึ้นแล้วจะเท่ากับจำนวนสี

กราฟนี้ไม่ใช่กราฟที่ถ่ายทอดจุดยอดได้ (vertex-transitive ): กลุ่มออโตมอร์ฟิซึม ของกราฟนี้ มีวงโคจรหนึ่งวงบนจุดยอดที่มีขนาด 8 และอีกหนึ่งวงบนจุดยอดที่มีขนาด 4

กราฟ Chvátal เป็นกราฟแฮมิลโทเนียนและมีบทบาทสำคัญในการพิสูจน์โดยFleischner & Sabidussi (2002) ว่า การกำหนดว่ากราฟแฮมิลโทเนียนที่ไม่มีสามเหลี่ยมสามารถระบายสีได้ 3 สีหรือไม่นั้นเป็นปัญหาNP-complete ^{[ 5 ]}

พหุนามลักษณะเฉพาะของกราฟ Chvátal คือ${\displaystyle (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$พหุนาม Tutteของกราฟ Chvátal ได้รับการคำนวณโดยBjörklund et al. (2008 ) ^{[ 6 ]}

ค่าความเป็นอิสระของกราฟนี้คือ 4

กราฟเป็นระนาบ1 ^{[ 7 ]}

• 
  จำนวนสีของกราฟ Chvátal คือ 4
• 
  ดัชนีสีของกราฟ Chvátal คือ 4
• 
  กราฟ Chvátal เป็นกราฟแฮมิลโทเนียน
• 
  ภาพวาดอีกแบบหนึ่งของกราฟ Chvátal
• 
  1-ภาพวาดระนาบของกราฟ Chvátal