| dbo:abstract
|
- 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ő. 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. (hu)
- 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ő. 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. (hu)
|
