În teoria grafurilor, numărul Hadwiger al unui graf nedirecționat G este dimensiunea celui mai mare graf complet care poate fi obținut prin contractarea muchiilor lui G . În mod echivalent, numărul Hadwiger h ( G ) este cel mai mare număr k pentru care graficul complet K k este minor al lui G , graficul mai mic obținut din G prin contractarea muchiilor și eliminând vârfuri și muchii. Numărul Hadwiger mai este cunoscut și sub denumirea de numărul de contracție a clicei a graficului G [1] sau gradul de omomorfism al graficului G [2] . Numărul este numit după Hugo Hadwiger , care a introdus numărul în 1943 și a presupus că numărul Hadwiger este întotdeauna cel puțin numărul cromatic al graficului G.
Graficele cu un număr Hadwiger de 4 sau mai puțin sunt descrise de Wagner [3] . Graficele cu orice număr Hadwiger finit sunt rare și au un număr cromatic mic. Determinarea numărului Hadwiger pentru un grafic este NP-hard , dar problema poate fi rezolvată cu parametri fix.
Un grafic G are un număr Hadwiger de cel mult 2 dacă și numai dacă este o pădure și un minor complet cu trei vârfuri poate fi format prin contractarea unui ciclu în G .
Un grafic are un număr Hadwiger de trei sau mai puțin dacă și numai dacă lățimea arborelui său nu depășește doi, ceea ce este valabil dacă și numai dacă oricare dintre balamalele sale este un grafic paralel-serial .
Din teorema lui Wagner , care descrie grafurile plane prin subgrafele lor interzise , rezultă că grafurile plane au un număr Hadwiger care nu depășește 4. În unele articole care conțin demonstrarea teoremei, Wagner [3] descrie grafuri cu un număr Hadwiger de patru sau mai puțin. mai precis - acestea sunt grafice, care pot fi formate folosind operații sum-cu-clică ale grafurilor plane cu un graf Wagner având 8 vârfuri.
Graficele cu un număr Hadwiger mai mic de cinci includ grafice cu vârfuri și grafice încorporabile fără legături , ambele familii au un grafic complet K 6 printre minorii interziși [4]
Orice grafic cu n vârfuri și numărul Hadwiger k are muchii O( nk √ log k ). Această limită este exactă — pentru orice k , există un grafic cu numărul Hadwiger k care are muchii Ω( nk √ log k ) [5] [6] [7] . Dacă un grafic G are un număr Hadwiger k , atunci toate subgrafele sale au și un număr Hadwiger cel mult k , iar acest lucru implică faptul că graficul G trebuie să aibă degenerare O( k √ log k ). Astfel, graficele cu un număr Hadwiger mărginit sunt grafice rare .
Conjectura Hadwiger afirmă că numărul Hadwiger este întotdeauna cel puțin numărul cromatic al graficului G. Adică, orice grafic cu un număr Hadwiger k ar trebui să aibă o colorare cu cel mult k culori. Cazul k = 4 este echivalent (prin caracterizarea lui Wagner a graficelor cu acest număr Hadwiger) cu problema cu patru culori a colorării graficelor plane . Ipoteza a fost demonstrată și pentru k ≤ 5, dar rămâne nedovedită pentru valori mari ale lui k [8]
Datorită densității scăzute, graficele cu un număr Hadwiger care nu depășește k pot fi colorate folosind algoritmul de colorare greedy în culori O( k √ log k ).
Verificarea dacă numărul Hadwiger al unui grafic dat este mai mare decât o valoare k este o problemă NP-completă [9] , ceea ce implică că determinarea numărului Hadwiger este o problemă NP-hard . Cu toate acestea, problema este rezolvată-parametric — există un algoritm pentru determinarea celui mai mare clic minor în timp, depinzând doar polinom de mărimea graficului, dar exponențial de h ( G ) [10] . În plus, algoritmii de timp polinomial pot aproxima numărul Hadwiger mult mai precis decât cea mai bună aproximare a timpului polinomial (presupunând P ≠ NP) a mărimii celor mai mari subgrafe complete [10] .
Numărul acromatic al unui grafic G este mărimea celei mai mari clicuri care se poate forma prin contractarea unei familii de mulțimi independente în G .
Minorii nenumărabili de clicuri în grafice infinite pot fi caracterizați în termeni de adăposturi , care formalizează strategiile de evaziune pentru unele jocuri de urmărire-evitare - dacă numărul Hadwiger este nenumărabil, este egal cu ordinea celui mai mare adăpost din grafic [11] .
Orice grafic cu numărul Hadwiger k are cel mult n 2 O( k log log k ) clicuri ( subgrafe complete) [12] .
Halin [2] a definit o clasă de parametri de grafic, pe care i-a numit S - funcții. Printre acestea se numără și numărul Hadwiger. Aceste funcții de mapare a graficelor la numere întregi trebuie să ia zero pe graficele fără margini , să fie monotone minore , să crească cu unu atunci când se adaugă un nou vârf adiacent tuturor nodurilor anterioare și din două valori pentru subgrafele de pe ambele părți ale separatorului clicei funcția ar trebui să capete o valoare mai mare. Setul de astfel de funcții formează o rețea completăprin operaţii de luare a elementelor minime sau maxime. Elementul de jos într-o astfel de rețea este numărul Hadwiger, iar elementul de sus este lățimea arborelui .