Podbarvení - Subcoloring

Neoptimální podbarvení se čtyřmi barvami. Sloučením červené a modré barvy a zelené a žluté barvy vznikne podbarvení pouze se dvěma barvami.

v teorie grafů, a podbarvení je úkolem barvy do a graf je vrcholy takové, že každá barevná třída indukuje vrchol disjunktní unie kliky. To znamená, že každá barevná třída by měla tvořit a shlukový graf.

The subchromatické číslo χ_S(G) grafu G je nejméně barev potřebných pro jakékoli podbarvení G.

Subcoloring a subchromatic number byly zavedeny Albertson a kol. (1989).

Každý správné zbarvení a barvení grafu jsou také podbarvení, takže subchromatické číslo libovolného grafu se maximálně rovná kochromatickému číslu, které se maximálně rovná chromatickému číslu.

Podbarvení je stejně obtížné vyřešit přesně jako barvení, v tom smyslu, že (jako barvení) je NP-kompletní. Přesněji řečeno, problém zjistit, zda a rovinný graf má subchromatické číslo nejvýše 2 je NP-úplné, i když je

• bez trojúhelníků graf s maximem stupeň 4 (Gimbel & Hartman 2003 ) (Fiala a kol. 2003 ),
• srovnávací graf s maximálním stupněm 4 (Ochem 2017 ),
• hranový graf bipartitního grafu s maximálním stupněm 4 (Gonçalves & Ochem 2009 ),
• graf s obvod 5 (Montassier & Ochem 2015 ).

Subchromatické číslo a cograph lze vypočítat v polynomiálním čase (Fiala a kol. 2003 ). Pro každé pevné celé číslo r je možné v polynomiálním čase rozhodnout, zda bude subchromatický počet interval a permutace grafy je maximálně r (Broersma a kol. 2002 ).

Reference

• Albertson, M. O .; Jamison, R.E .; Hedetniemi, S. T .; Locke, S. C. (1989), „Subchromatické číslo grafu“, Diskrétní matematika, 74 (1–2): 33–49, doi:10.1016 / 0012-365X (89) 90196-9.
• Broersma, Hajo; Fomin, Fedor V .; Nesetril, Jaroslav; Woeginger, Gerhard (2002), „Více o podbarvování“, Výpočetní, 69 (3): 187–203, doi:10.1007 / s00607-002-1461-1.
• Fiala, J .; Klaus, J .; Le, V. B .; Seidel, E. (2003), „Podbarvení grafů: složitost a algoritmy“, SIAM Journal on Discrete Mathematics, 16 (4): 635–650, CiteSeerX  10.1.1.3.183, doi:10.1137 / S0895480101395245.
• Gimbel, John; Hartman, Chris (2003), „Subcolorings and the subchromatic number of a graph“, Diskrétní matematika, 272 (2–3): 139–154, doi:10.1016 / S0012-365X (03) 00177-8.
• Gonçalves, Daniel; Ochem, Pascal (2009), „O hvězdné a housenkové arboricitě“, Diskrétní matematika, 309 (11): 3694–3702, doi:10.1016 / j.disc.2008.01.041.
• Montassier, Mickael; Ochem, Pascal (2015), „Near-Colours: Non-Colorable Graphs and NP-Complete.“, Electronic Journal of Combinatorics, 22 (1): # P1.57.
• Ochem, Pascal (2017), „2-subcoloring is NP-complete for planar comparability graphs“, Dopisy o zpracování informací, 128: 46–48, arXiv:1702.01283, doi:10.1016 / j.ipl.2017.08.004.