Construcția Hajos este o operație grafică numită după matematicianul maghiar György Hajos [1] , care poate fi folosită pentru a construi orice graf critic sau orice graf al cărui număr cromatic este cel puțin un anumit prag dat.
Fie G și H două grafice nedirecționate , vw o muchie în G și xy o muchie în H. Apoi construcția lui Hayosh formează un nou grafic care combină două grafice combinând vârfurile v și x într-un singur vârf, eliminând muchiile vw și xy și adăugând o nouă muchie wy .
De exemplu, fie G și H două grafice complete K 4 cu patru vârfuri. Având în vedere simetria acestor grafice, alegerea muchiilor din aceste grafice nu este esențială. În acest caz, rezultatul aplicării construcției lui Hajosh va fi axul Moser , un grafic de distanță cu șapte noduri care necesită patru culori pentru a colora.
Un alt exemplu, dacă G și H sunt două cicluri de lungime p și , respectiv, q , atunci rezultatul aplicării construcției Hyos va fi din nou un ciclu de lungime p + q − 1 .
Se spune că un grafic G k este constructibil (sau k -constructibil conform lui Hajosh) dacă este format într-unul din trei moduri [2] :
Este suficient să arătăm simplu că orice grafic k -constructibil necesită cel puțin k culori pentru a colora corect graficul. Într-adevăr, acest lucru este destul de clar pentru graficul complet K k , iar rezultatul unirii a două vârfuri neadiacente le obligă să fie colorate în aceeași culoare în orice colorare, ceea ce nu reduce numărul de culori. În construcția Hajosh în sine, noua muchie wy face ca cel puțin unul dintre cele două vârfuri w și y să aibă o culoare diferită de culoarea vârfului obținut prin unirea vârfurilor v și x , astfel încât orice colorare corectă a vârfurilor graficul combinat are ca rezultat o colorare corectă a unuia dintre cele două grafice mai mici, din care a fost obținut graficul, din care iarăși obținem nevoia de k culori [2] .
Haios a dovedit o afirmație mai riguroasă că un graf necesită cel puțin k culori în orice colorare adecvată dacă și numai dacă conține un graf k -constructibil ca subgraf. În mod echivalent, orice k -graf critic ( un grafic care necesită k culori, dar orice subgraf propriu care necesită mai puține culori) este k - constructibil [3] . Alternativ, orice graf care necesită k culori poate fi format prin combinarea construcției Hayosh, a operațiilor de unire a două vârfuri neadiacente și a operațiilor de adăugare a vârfurilor sau a muchiilor la un graf dat, începând cu un grafic complet K k [4] .
O construcție similară poate fi folosită pentru colorarea prescrisă în locul colorării obișnuite [5] [6] .
Pentru k =3, orice graf k -critic (adică orice ciclu impar) poate fi construit ca un graf k -constructibil în așa fel încât toate graficele formate în timpul construcției sale să fie și k -critice. Pentru k =8 , acest lucru nu este adevărat – graficul pe care Catlin [7] l-a găsit ca contraexemplu pentru conjectura lui Hadwiger că un graf k - cromatic este contractibil cu un grafic complet K k este un contraexemplu pentru această problemă. Ulterior, graficele k -critice, dar nu k -constructibile au fost găsite numai exclusiv prin intermediul k -grafice critice, pentru toate k ≥ 4 . Pentru k =4 , un astfel de exemplu se obține din graficul dodecaedrului prin adăugarea unei noi muchii la fiecare pereche de vârfuri antipodale [8] .
Deoarece unirea a două vârfuri neadiacente reduce numărul de vârfuri din graficul rezultat, numărul de operații necesare pentru a reprezenta un anumit grafic G folosind operațiile definite de Hyosz nu poate depăși numărul de vârfuri din G [9] .
Mansfield și Welsh [10] definesc numărul Hajosh h ( G ) al unui grafic k -cromatic G ca numărul minim de pași necesari pentru a construi G din K k , unde la fiecare pas se formează un nou grafic prin combinarea a două grafice formate anterior , combinând două vârfuri neadiacente ale formatei înaintea unui graf sau adăugând o muchie la un graf format anterior. Ei au arătat că pentru un grafic G cu n vârfuri și m muchii , h ( G ) ≤ 2 n 2 /3 − m + 1 − 1 . Dacă orice grafic are un număr Hayosh polinomial, rezultă că este posibil să se dovedească incolorabilitatea în timp polinomial nedeterminist și, prin urmare, rezultă că NP = co-NP , ceea ce este considerat improbabil de către teoreticienii complexității algoritmilor [11] . Cu toate acestea, nu se știe cum să se demonstreze limitele inferioare nepolinomiale pentru numerele Hajos fără anumite presupuneri despre complexitatea teoretică și, dacă astfel de limite sunt dovedite, existența limitelor nepolinomiale pentru unele tipuri de sisteme Frege în matematică . logica [11] va urma imediat .
Dimensiunea minimă a unui arbore de expresii care descrie construcția Hyos pentru un anumit grafic G poate fi substanțial mai mare decât numărul Hyos al graficului G , deoarece cea mai mică expresie pentru G poate reutiliza aceleași grafice de mai multe ori (economiile nu sunt permise în un arbore de expresie). Există grafice 3-cromatice pentru care cel mai mic astfel de arbore de expresie are dimensiune exponențială [12] .
Köster [13] a folosit construcția Hajos pentru a obține un set infinit de grafice poliedrice cu 4 critici , fiecare cu de două ori mai multe muchii decât vârfuri. În mod similar, Liu și Zhang [14] au folosit o construcție care începe cu graficul Grötsch pentru a obține multe grafice fără triunghiuri critice , despre care au arătat că sunt dificil de găsit colorări cu algoritmii tradiționali de backtracking .
În combinatoria poliedrelor, Reinhard Euler [15] a folosit construcția Hajos pentru a genera fațete ale unui set politop stabil .