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

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

ในการศึกษาปัญหาสำคัญและยากต่างๆ ในทฤษฎีกราฟ (เช่น สมมติฐานการ ครอบคลุมสองเท่าของวัฏจักรและสมมติฐานการไหล 5 ) จะพบกราฟประเภทหนึ่งที่น่าสนใจแต่ค่อนข้างลึกลับเรียกว่า snarks แม้จะมีคำจำกัดความที่เรียบง่าย...และมีการศึกษามานานกว่าศตวรรษ คุณสมบัติและโครงสร้างของพวกมันก็ยังไม่เป็นที่รู้จักมากนัก^{[ 1 ]}

นอกจากปัญหาที่พวกเขากล่าวถึงแล้วข้อสันนิษฐานเรื่อง snarkของWT Tutteยังเกี่ยวข้องกับการมีอยู่ของกราฟ Petersenในฐานะกราฟย่อยของ snark ซึ่งมีการประกาศการพิสูจน์มานานแล้วแต่ยังไม่ได้ตีพิมพ์ และจะยุติกรณีพิเศษของการมีอยู่ของ4-flow ที่ไม่มีที่ใดเป็นศูนย์

Snarks were so named by the American mathematician Martin Gardner in 1976, after the mysterious and elusive object of the poem The Hunting of the Snark by Lewis Carroll.^[2] However, the study of this class of graphs is significantly older than their name. Peter G. Tait initiated the study of snarks in 1880, when he proved that the four color theorem is equivalent to the statement that no snark is planar.^[3] The first graph known to be a snark was the Petersen graph; it was proved to be a snark by Julius Petersen in 1898,^[4] although it had already been studied for a different purpose by Alfred Kempe in 1886.^[5]

The next four known snarks were

• the Blanuša snarks (two with 18 vertices), discovered by Danilo Blanuša in 1946,^[6]
• the Descartes snark (210 vertices), discovered by Bill Tutte in 1948,^[7] and
• the Szekeres snark (50 vertices), discovered by George Szekeres in 1973.^[8]

In 1975, Rufus Isaacs generalized Blanuša's method to construct two infinite families of snarks: the flower snarks and the Blanuša–Descartes–Szekeres snarks, a family that includes the two Blanuša snarks, the Descartes snark and the Szekeres snark. Isaacs also discovered a 30-vertex snark that does not belong to the Blanuša–Descartes–Szekeres family and that is not a flower snark: the double-star snark.^[9] Another infinite family, the Loupekine snarks, was published by Isaacs in 1976, credited to F. Loupekine. It includes two 22-vertex snarks derived from the Petersen graph.^[10] The 50-vertex Watkins snark was discovered in 1989.^[11]

กราฟลูกบาศก์ที่ไม่สามารถระบายสีขอบได้สามสีที่น่าสนใจอีกกราฟหนึ่งคือกราฟของ Tietzeซึ่งมี 12 จุดยอด ดังที่Heinrich Franz Friedrich Tietzeค้นพบในปี 1910 กราฟนี้เป็นขอบเขตของการแบ่งย่อยของแถบโมเบียสที่ต้องใช้หกสี^{[ 12 ]}อย่างไรก็ตาม เนื่องจากมีรูปสามเหลี่ยมอยู่ด้วย จึงโดยทั่วไปแล้วไม่ถือว่าเป็น snark ตามคำจำกัดความที่เข้มงวดของ snark กราฟ snark ที่เล็กที่สุดคือกราฟ Petersen และ snark ของ Blanuša ตามด้วย snark 20 จุดยอดที่แตกต่างกันหกแบบ^{[ 13 ]}

รายการ snark ทั้งหมดที่มีจุดยอดไม่เกิน 36 จุด (ตามคำจำกัดความที่เข้มงวด) และไม่เกิน 34 จุด (ตามคำจำกัดความที่อ่อนกว่า) ถูกสร้างขึ้นโดย Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund และ Klas Markström ในปี 2012 ^{[ 13 ]}จำนวน snark สำหรับจำนวนจุดยอดคู่ที่กำหนดจะเพิ่มขึ้นอย่างน้อยแบบเลขชี้กำลังตามจำนวนจุดยอด^{[ 14 ]} (เนื่องจากมีจุดยอดที่มีดีกรีคี่ snark ทั้งหมดจึงต้องมีจำนวนจุดยอดคู่ตามเลมมาการจับมือ ) ^{[ 15 ]} ลำดับOEIS A130315ประกอบด้วยจำนวน snark ที่ไม่ใช่จุดยอดธรรมดาสำหรับค่าเล็กๆของ^{[ 16 ]}${\displaystyle 2n}$${\displaystyle n}$

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

• ถ้ากราฟลูกบาศก์มีสะพานซึ่งเป็นขอบที่หากลบออกจะทำให้ขาดการเชื่อมต่อ กราฟนั้นจะไม่สามารถเป็นกราฟชั้นหนึ่งได้ ตามทฤษฎีบทการจับมือกราฟย่อยที่อยู่ทั้งสองด้านของสะพานจะมีจำนวนจุดยอดเป็นเลขคี่ ไม่ว่าจะเลือกสีใดในสามสีสำหรับสะพาน จำนวนจุดยอดที่เป็นเลขคี่ของกราฟย่อยเหล่านี้จะป้องกันไม่ให้กราฟย่อยเหล่านี้ถูกปกคลุมด้วยวัฏจักรที่สลับกันระหว่างสองสีที่เหลือ ซึ่งจำเป็นในกรณีการระบายสีขอบ 3 สี ด้วยเหตุนี้ โดยทั่วไปแล้ว snarks จะต้องไม่มีสะพาน^{[ 2 ] [ 9 ]}
• ลูป (ขอบที่เชื่อมจุดยอดกับตัวเอง) ไม่สามารถระบายสีได้โดยไม่ทำให้สีเดียวกันปรากฏซ้ำสองครั้งที่จุดยอดนั้น ซึ่งเป็นการละเมิดข้อกำหนดปกติสำหรับการระบายสีขอบกราฟ นอกจากนี้ วงจรที่ประกอบด้วยจุดยอดสองจุดที่เชื่อมต่อกันด้วยขอบสองเส้น สามารถแทนที่ด้วยขอบเส้นเดียวที่เชื่อมจุดยอดข้างเคียงอีกสองจุดได้เสมอ ทำให้กราฟง่ายขึ้นโดยไม่เปลี่ยนแปลงความสามารถในการระบายสีขอบสามเส้น ด้วยเหตุผลเหล่านี้ snarks จึงมักถูกจำกัดไว้เฉพาะกราฟแบบง่ายกราฟที่ไม่มีลูปหรือการเชื่อมต่อหลายจุด^{[ 9 ]}
• ถ้ากราฟมีรูปสามเหลี่ยม ก็สามารถลดรูปกราฟนั้นได้อีกครั้งโดยไม่เปลี่ยนแปลงความสามารถในการระบายสีขอบสามด้าน โดยการยุบจุดยอดทั้งสามของรูปสามเหลี่ยมให้เป็นจุดยอดเดียว ดังนั้น นิยามของ snark หลายๆ นิยามจึงห้ามใช้รูปสามเหลี่ยม^{[ 9 ]}อย่างไรก็ตาม แม้ว่าข้อกำหนดนี้จะระบุไว้ในงานของ Gardner ที่ให้ชื่อ "snark" แก่กราฟเหล่านี้ แต่ Gardner ก็ระบุกราฟของ Tietzeซึ่งมีรูปสามเหลี่ยมอยู่ด้วยว่าเป็น snark ^{[ 2 ]}
• หากกราฟมีวงจรสี่จุดยอด สามารถลดรูปได้สองวิธีที่แตกต่างกัน โดยการลบขอบตรงข้ามสองขอบของวงจรออก และแทนที่เส้นทางที่ได้ของจุดยอดดีกรีสองด้วยขอบเดี่ยว กราฟจะมีสีขอบสามสีก็ต่อเมื่อการลดรูปอย่างน้อยหนึ่งวิธีนี้ทำได้ ดังนั้น Isaacs จึงต้องการกราฟลูกบาศก์คลาสสองที่ "ไม่ธรรมดา" เพื่อหลีกเลี่ยงวงจรสี่จุดยอด^{[ 9 ]}และผู้เขียนคนอื่นๆ ก็ได้ปฏิบัติตามในการห้ามวงจรเหล่านี้^{[ 13 ]}ข้อกำหนดที่ว่า snark ต้องหลีกเลี่ยงวงจรที่มีความยาวสี่หรือน้อยกว่านั้น สามารถสรุปได้โดยการระบุว่าเส้นรอบวงของกราฟเหล่านี้ ความยาวของวงจรที่สั้นที่สุด ต้องมีอย่างน้อยห้า
• ยิ่งไปกว่านั้น คำจำกัดความที่ใช้โดยBrinkmann et al. (2012)กำหนดให้ snark ต้องมีขอบเชื่อมต่อแบบวนรอบ 4 ขอบ นั่นหมายความว่าต้องไม่มีเซตย่อยที่มีขอบสามขอบหรือน้อยกว่า ซึ่งการลบขอบเหล่านั้นจะทำให้กราฟแยกออกเป็นสองกราฟย่อย โดยแต่ละกราฟย่อยจะมีอย่างน้อยหนึ่งวงจร Brinkmann et al. กำหนดให้ snark เป็นกราฟลูกบาศก์ที่มีขอบเชื่อมต่อแบบวนรอบ 4 ขอบ มีเส้นรอบวงห้าหรือมากกว่า และคลาสสอง พวกเขากำหนด "snark แบบอ่อน" ให้สามารถมีเส้นรอบวงสี่ได้^{[ 13 ]}

แม้ว่าคำจำกัดความเหล่านี้จะพิจารณาเฉพาะข้อจำกัดเกี่ยวกับเส้นรอบวงไม่เกินห้า แต่งูที่มีเส้นรอบวงใหญ่ตามอำเภอใจก็มีอยู่^{[ 17 ]}

งานของ Peter G. Tait ได้พิสูจน์ว่าทฤษฎีบทสี่สีเป็นจริงก็ต่อเมื่อ snark ทุกตัวไม่ใช่ระนาบ^{[ 3 ]}ทฤษฎีบทนี้ระบุว่ากราฟระนาบทุกตัวมีการระบายสีกราฟของจุดยอดด้วยสี่สี แต่ Tait ได้แสดงวิธีการแปลงการระบายสีจุดยอด 4 สีให้กับกราฟระนาบสูงสุดให้เป็นการระบายสีขอบ 3 สีให้กับกราฟคู่ ของมัน ซึ่งเป็นกราฟลูกบาศก์และกราฟระนาบ และในทางกลับกัน ดังนั้น snark ระนาบจึงจำเป็นต้องเป็นคู่ของตัวอย่างค้านของทฤษฎีบทสี่สี ดังนั้น การพิสูจน์ทฤษฎีบทสี่สีในภายหลัง^{[ 18 ]}จึงแสดงให้เห็นว่า snark ทั้งหมดไม่ใช่ระนาบ^{[ 19 ]}

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

ข้อสันนิษฐานเรื่องการครอบคลุมสองชั้นของวงจรระบุว่า ในกราฟที่ไม่มีสะพานทุกกราฟ เราสามารถหาชุดของวงจรที่ครอบคลุมขอบแต่ละขอบสองครั้ง หรือเทียบเท่ากับว่ากราฟสามารถฝังลงบนพื้นผิวได้ในลักษณะที่ทุกหน้าของการฝังเป็นวงจรแบบง่าย เมื่อกราฟลูกบาศก์มีการระบายสีขอบ 3 สี กราฟนั้นจะมีการครอบคลุมสองชั้นของวงจรซึ่งประกอบด้วยวงจรที่เกิดจากสีแต่ละคู่ ดังนั้น ในบรรดากราฟลูกบาศก์ กราฟ snark จึงเป็นตัวอย่างค้านที่เป็นไปได้เพียงอย่างเดียว โดยทั่วไปแล้ว กราฟ snark เป็นกรณีที่ยากสำหรับข้อสันนิษฐานนี้: หากเป็นจริงสำหรับกราฟ snark ก็จะเป็นจริงสำหรับกราฟทั้งหมด^{[ 21 ]}ในเรื่องนี้Branko Grünbaumตั้งข้อสันนิษฐานว่าไม่มีกราฟ snark ใดที่สามารถฝังลงบนพื้นผิวได้ในลักษณะที่ทุกหน้าเป็นวงจรแบบง่าย และทุกสองหน้าจะไม่ทับซ้อนกันหรือมีขอบร่วมกันเพียงขอบเดียว หากกราฟ snark ใดมีการฝังแบบนั้น หน้าของมันจะก่อให้เกิดการครอบคลุมสองชั้นของวงจร อย่างไรก็ตาม Martin Kochol ได้ค้นพบตัวอย่างค้านต่อสมมติฐานของ Grünbaum ^{[ 22 ]}

การพิจารณาว่ากราฟลูกบาศก์ที่เชื่อมต่อแบบวนรอบ 5 เส้นที่กำหนดนั้นสามารถระบายสีขอบได้ 3 สีหรือไม่นั้นเป็นปัญหาNP-completeดังนั้น การพิจารณาว่ากราฟเป็น snark หรือไม่จึงเป็นปัญหาco-NP- complete ^{[ 23 ]}

WT Tutteตั้งข้อสันนิษฐานว่า snark ทุกอันมีกราฟ Petersen เป็นminorนั่นคือ เขาตั้งข้อสันนิษฐานว่า snark ที่เล็กที่สุด กราฟ Petersen อาจถูกสร้างขึ้นจาก snark อื่นๆ โดยการยุบขอบบางส่วนและลบขอบอื่นๆ ออก หรือเทียบเท่า (เนื่องจากกราฟ Petersen มีดีกรีสูงสุดสาม) snark ทุกอันมี subgraph ที่สามารถสร้างขึ้นจากกราฟ Petersen โดยการแบ่งขอบบางส่วนข้อสันนิษฐานนี้เป็นรูปแบบที่แข็งแกร่งขึ้นของทฤษฎีบทสี่สีเนื่องจากกราฟใดๆ ที่มีกราฟ Petersen เป็น minor จะต้องไม่ใช่กราฟระนาบ ในปี 1999 Neil Robertson , Daniel P. Sanders , Paul SeymourและRobin Thomasได้ประกาศการพิสูจน์ข้อสันนิษฐานนี้^{[ 24 ]}ขั้นตอนต่างๆ ที่นำไปสู่ผลลัพธ์นี้ได้รับการตีพิมพ์ในปี 2016 และ 2019 ^{[ 25 ] [ 26 ]}แต่การพิสูจน์ที่สมบูรณ์ยังไม่ได้รับการตีพิมพ์^{[ 19 ]}ดูสมมติฐานของ Hadwigerสำหรับปัญหาและผลลัพธ์อื่นๆ ที่เกี่ยวข้องกับการระบายสีกราฟกับไมเนอร์กราฟ

Tutte ยังตั้งข้อสันนิษฐานถึงการวางนัยทั่วไปสำหรับกราฟใดๆ อีกด้วย: กราฟที่ไม่มีสะพานทุกกราฟที่ไม่มี Petersen minor จะมี4-flow ที่ไม่มีที่ใดเป็นศูนย์นั่นคือ ขอบของกราฟอาจถูกกำหนดทิศทางและตัวเลขจากเซต {1, 2, 3} โดยที่ผลรวมของตัวเลขขาเข้าลบด้วยผลรวมของตัวเลขขาออกที่แต่ละจุดยอดหารด้วยสี่ลงตัว ดังที่ Tutte แสดงให้เห็น สำหรับกราฟลูกบาศก์ การกำหนดดังกล่าวจะมีอยู่ก็ต่อเมื่อขอบสามารถระบายสีได้ด้วยสามสี ดังนั้นข้อสันนิษฐานจึงเป็นผลมาจากข้อสันนิษฐาน snark ในกรณีนี้ อย่างไรก็ตาม การพิสูจน์ข้อสันนิษฐาน snark จะไม่สามารถแก้ปัญหาเรื่องการมีอยู่ของ 4-flow สำหรับกราฟที่ไม่ใช่ลูกบาศก์ได้^{[ 27 ]}

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับSnarks (ทฤษฎีกราฟ )

• ไวส์สไตน์, เอริค ดับเบิลยู. , "เสียดสี" , แมธเวิลด์
• รวมคลิปเสียดสีต่างๆจาก House of Graphs