Erős színezés

A matematika, azon belül a gráfelmélet területén ha egy gráf csúcsainak létezik azonos méretű, diszjunkt részekre osztása, akkor erős színezés (strong coloring) alatt olyan (jó) csúcsszínezés értendő, melyben minden szín minden partícióban pontosan egyszer szerepel. Ha a G gráf rendje nem osztható k-val, hozzáadandó annyi izolált csúcs, amivel az új G′ rendje k-val oszthatóvá válik. Ebben az esetben a G′ erős színezése a hozzáadott izolált csúcsok nélkül tekinthető G erős színezésének. Egy gráf erősen k-színezhető, ha csúcsainak bármely k méretű részekre osztása esetén erősen színezhető.

Az ábrán látható Möbius-létra erősen 4-színezhető. 35 darab 4 csúcs méretű partícióra osztható fel, de ezek közül csak 7 felosztás különbözik egymástól topológiailag.

A G gráf erős kromatikus száma, sχ(G) az a legkisebb k, amire G erősen k-színezhető. Egy gráf erősen k-kromatikus, ha erős kromatikus száma k.

A sχ(G) néhány tulajdonsága:

1. sχ(G) > Δ(G).
2. sχ(G) ≤ 3 Δ(G) − 1 (Haxell)
3. Aszimptotikusan sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell)

Itt Δ(G) a maximális fokszáma.

Az erős kromatikus számot egymástól függetlenül Alon (1988) és Fellows (1990) vezette be.

Fordítás

• Ez a szócikk részben vagy egészben a Strong coloring 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

• (1988) „The linear arboricity of a graph”. Israel J. Math. 62 (3), 311–325. o. DOI:10.1007/BF02783300. 
• (1992) „The strong chromatic number”. Random Structures and Algorithms 3, 1–7. o. DOI:10.1002/rsa.3240030102. 
• (1990) „Transversals of vertex partition in graphs”. SIAM Journal on Discrete Mathematics 3 (2), 206–215. o. DOI:10.1137/0403018. 
• (2004) „On the strong chromatic number”. Combinatorics, Probability and Computing 13, 857–865. o. DOI:10.1017/S0963548304006157. 
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.