Részszínezés

Egy gráf nem optimális, négy színt használó részszínezése. A piros és kék, illetve a zöld és sárga színeket összevonva mindössze két színnel is lehetséges a részszínezés.

A matematika, azon belül a gráfelmélet területén egy gráf részszínezése (subcoloring) a gráf csúcsaihoz színek rendelése oly módon, hogy minden színosztály klikkek diszjunkt unióját feszítse ki a gráfban – tehát minden színosztály egy-egy klasztergráfot alkosson.

A G gráfhoz tartozó χ_S(G) részkromatikus szám (subchromatic number) a G részszínezéséhez minimálisan szükséges színek száma. A részszínezést és a részkromatikus számot (Albertson et al. 1989) vezette be.

Egy gráf minden jó színezése és komplementer színezése egyben részszínezés is, így egy gráf részkromatikus száma legfeljebb a komplementer kromatikus számmal egyezik meg, ami viszont legfeljebb a kromatikus számmal.

A részszínezési probléma pontosan olyan nehéz, mint a színezésé, NP-nehéz. Annak megállapítása, hogy egy síkbarajzolható gráf részkromatikus száma legfeljebb 2-e, még akkor is NP-teljes, ha a szóban forgó gráf:

• háromszögmentes, maximális fokszáma 4 (Gimbel & Hartman 2003) (Fiala et al. 2003),
• összehasonlíthatósági gráf, 4 maximális fokszámmal (Ochem 2017),
• páros gráf élgráfja, 4 maximális fokszámmal (Gonçalves & Ochem 2009),
• 5 girthparaméterű (Montassier & Ochem 2015).

Egy kográf részkromatikus száma ellenben polinom időben kiszámítható (Fiala et al. 2003). Bármely rögzített r egészre polinom időben eldönthető, hogy adott intervallumgráf vagy permutációgráf részkromatikus száma legfeljebb r-e (Broersma et al. 2002).

Fordítás

• Ez a szócikk részben vagy egészben a Subcoloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Albertson, M. O.; Jamison, R. E. & Hedetniemi, S. T. et al. (1989), "The subchromatic number of a graph", Discrete Mathematics 74 (1–2): 33–49, DOI 10.1016/0012-365X(89)90196-9.
• Broersma, Hajo; Fomin, Fedor V. & Nesetril, Jaroslav et al. (2002), "More About Subcolorings", Computing 69: 187–203, DOI 10.1007/s00607-002-1461-1.
• Fiala, J.; Klaus, J. & Le, V. B. et al. (2003), "Graph Subcolorings: Complexity and Algorithms", SIAM Journal on Discrete Mathematics 16 (4): 635–650, DOI 10.1137/S0895480101395245.
• Gimbel, John & Hartman, Chris (2003), "Subcolorings and the subchromatic number of a graph", Discrete Mathematics 272 (2–3): 139–154, DOI 10.1016/S0012-365X(03)00177-8.
• Gonçalves, Daniel & Ochem, Pascal (2009), "On star and caterpillar arboricity", Discrete Mathematics 309 (11): 3694–3702, DOI 10.1016/j.disc.2008.01.041.
• Montassier, Mickael & Ochem, Pascal (2015), "Near-Colorings: Non-Colorable Graphs and NP-Completeness", Electronic Journal of Combinatorics 22 (1): #P1.57, <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p57>.
• Ochem, Pascal (2017), "2-subcoloring is NP-complete for planar comparability graphs", Information Processing Letters 128: 46–48, <http://www.sciencedirect.com/science/article/pii/S0020019017301461>.