У теорији графова, доматик подела графа ${\displaystyle G=(V,E)}$ је подела скупа чворова ${\displaystyle V_{1}}$ у дисјунктне скупове ${\displaystyle V_{2}}$,...,${\displaystyle V_{K}}$ такве да сваки V_i је доминантни скуп за G. Слика на десној страни приказује доматик поделу графа; овде је доминирајући скуп ${\displaystyle V_{1}}$ садржи жуте чворове, ${\displaystyle V_{2}}$ садржи зелене чворове и ${\displaystyle V_{3}}$ садржи плаве чворове.

Доматик број је максимална вредност доматик поделе, то јест, максимални број дисјунктних доминирајућих скупова. Граф на слици има доматик број 3. Лако је да се види да је доматик број бар 3 зато што смо направили доматик поделу вредности 3. Да би видели да је доматик број највише 3, прво показимо једноставну горњу границу.

Нека је ${\displaystyle \delta }$ минимални степен графа ${\displaystyle G}$. Доматик број од ${\displaystyle G}$ је највише ${\displaystyle \delta +1}$. Да би то показали, посматрајмо чвор ${\displaystyle v}$ степена ${\displaystyle \delta }$. Нека ${\displaystyle N}$ чине ${\displaystyle v}$ и његови суседни чворови. Знамо да (1) сваки доминирајући скуп ${\displaystyle V_{i}}$ мора садржати најмање један чвор из ${\displaystyle N}$ (доминација), и (2) сваки чвор у ${\displaystyle N}$ је садржан у највише једном доминирајућем скупу ${\displaystyle V_{i}}$ (дисјунктност). Дакле постоји највисе ${\displaystyle |N|=\delta +1}$ дисјунктних доминирајућих скупова.

Граф на слици има минимални степен ${\displaystyle \delta =2}$ и, дакле, његов доматик број је највише 3. Дакле, показали смо да је његов доматик број тачно 3; на слици је приказана доматик подела највеће величине.

Ако нема изолованих чворова у графу (што значи, ${\displaystyle \delta }$ ≥ 1), онда је доматик број најмање 2. Да би то видели, уочимо да је (1) слаба обојеност са две боје доматик подела ако нема изолованих чворова и (2) сваки граф има слабу обојеност са две боје. Алтернативно, (1) максимални независни скуп је доминирајући скуп и (2) комплемент максималног независног скупа је такође доминантни скуп ако нема изолованих чворова.

Слика на десној страни приказује слабу обојеност са две боје, која је такође доматик подела величине 2: тамни чворови чине доминирајући скуп, а светли чворови чине други доминирајући скуп (светли чворови формирају максимални независни скуп). Видети слабу обојеност за више информација.

Налажење доматик поделе величине 1 је тривијално: нека је ${\displaystyle V_{1}=V}$. Налажење доматик поделе величине 2 (или одређивање да она не постоји) је једноставно: проверити да ли постоје изоловани чворови, и ако не постоје, пронаћи слабу обојеност са две боје.

Дакако, налажење максималне величине доматик поделе је рачунски тешко. Специјално, следећи проблем одлучивања, познат као проблем доматик броја, је НП-комплетан: за дати граф ${\displaystyle G}$ и цео број ${\displaystyle K}$, одредити да ли је доматик број од ${\displaystyle G}$ најмање ${\displaystyle K}$. Дакле, проблем одређивања доматик броја датог графа је НП-тежак и проблем налаћења доматик поделе максималне величине је НП-тежак такође.

Постоји алгоритам полиномијалног времена са гарантованом логаритамском апроксимацијом^[1], то јест, могуће је наћи доматик поделу чија величина је оптимална до на фактор ${\displaystyle O(\log |V|)}$.

Дакако, не постоји приближни алгоритам полиномијалне сложености са подлогаритамским приближним фактором.^[1] Прецизније, приближни алгоритам полиномијалне слозености за доматик поделу са приближним фактором ${\displaystyle (1-\epsilon )\ln |V|}$ за константно ${\displaystyle \epsilon >0}$ би указало да сви НП проблеми могу бити решени у скоро супер-полиномијалној слозености ${\displaystyle n^{O(\log \log n)}}$.

Доматик подела

Подела чворова у дисјунктне доминирајуће скупове. Доматик број је максимални број оваквих скупова.

Бојење чворова

Подела чворова у дисјунктне независне скупове. Хроматски број је минимални број оваквих скупова.

Подела клика

Подела чворова у дисјунктне клике. Еквиваленто са бојењем чворова комплементарног графа.

Бојење ивица

Подела ивица на неповезана упарења. Хроматски број ивице је најмањи број ових скупова.

Нека је G = (U ∪ V, E) бипартитни граф без изолованих чворова; све ивице су облика {u, v} ∈ E и са u ∈ U v ∈ V. Тада, {U, V} је уједно и бојење чворова са две боје и доматик подела величине 2; скупови U и V су независни доминирајући скупови. Хроматски број од G је тачно 2; не постоји чвор бојење једном бојом. Доматик број од G је најмање 2. Могуће је да постоји већа доматик подела; на пример, комплетан бипартитан граф K_{n, n} за свако n ≥ 2 има доматик број n.

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 . A1.1: GT3, p. 190.
• Cockayne, E. J.; Hedetniemi, Stephen T. (1975), „Optimal domination in graphs”, IEEE Transactions on Circuits and Systems, CAS-22 (11): 855—857, MR 0384608, doi:10.1109/TCS.1975.1083994 .