Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

• ${\displaystyle k}$-критичний граф — це критичний граф із хроматичним числом k.
• Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом^[1].

• Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
  • G має тільки одну компоненту.
  • G — скінченний (теорема де Брёйна — Ердеша ^[2]).
  • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язний^[3].
  • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом K_k, або непарним циклом (теорема Брукса^[4]).
  • 2m ≥ (k − 1)n + k − 3^[5].
  • 2m ≥ (k − 1)n + [(k − 3)/(k² − 3)]n^[6].
  • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершин^[7]. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершини^[8].

• Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.

• 1-критичних графів не існує.
• Єдиний 2-критичний граф — це K_2.
• Всі 3-критичні графи вичерпуються простими циклами непарної довжини^[9].

• Як показав Хайош^[10], будь-який k-критичний граф можна сформувати з повного графу K_k комбінацією побудови Хайоша^[ru] з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.

• Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним^[11].

• Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є K_k єдиним двічі критичним k-хроматичним графом^[12].

• Фактор-критичний граф

• R. L. Brooks, W. T. Tutte. On colouring the nodes of a network // Proceedings of the Cambridge Philosophical Society. — 1941. — Т. 37, вип. 02 (12 листопада). — С. 194–197. — DOI:10.1017/S030500410002168X.
• N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54 (12 листопада). — С. 371–373.. (Indag. Math. 13.)
• G. A. Dirac. A theorem of R. L. Brooks and a conjecture of H. Hadwiger // Proceedings of the London Mathematical Society. — 1957. — Т. 7, вип. 1 (12 листопада). — С. 161–195. — DOI:10.1112/plms/s3-7.1.161.
• T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (12 листопада). — С. 165–192.
• T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (12 листопада). — С. 373–395..
• G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10 (12 листопада). — С. 116–117.
• T. R. Jensen, B. Toft. Graph coloring problems. — New York : Wiley-Interscience, 1995. — ISBN 0-471-02865-7.
• Matěj Stehlík. Critical graphs with connected complements // Journal of Combinatorial Theory. — 2003. — Т. 89, вип. 2 (12 листопада). — С. 189–194. — (Series B). — DOI:10.1016/S0095-8956(03)00069-8.
• László Lovász. Combinatorial Problems and Exercises (Second Edition). — North-Holland, 1992.
• Paul Erdős. In Theory of Graphs. — Proc. Colloq., Tihany, 1966. — С. 361.
• В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи Математических Наук. — 1968. — Т. XXIII, вип. 6 (144) (12 листопада). — С. 117–134.
• Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — ISBN 5-354-00301-6, ББК 22.144, 22.18, 22.19.