Stark färg
I grafteorin är en stark färgning , med avseende på en uppdelning av hörnen i (osammanhängande) delmängder av lika stora, en ( riktig) vertexfärgning där varje färg visas exakt en gång i varje del. En graf är starkt k -färgbar om den, för varje uppdelning av hörnen i uppsättningar av storlek k , tillåter en stark färgning. När ordningen på grafen G inte är delbar med k lägger vi till isolerade hörn till G precis tillräckligt för att göra ordningen för den nya grafen G′ delbar med k . I så fall anses en stark färgning av G′ minus de tidigare tillsatta isolerade hörnen vara en stark färgning av G .
Det starka kromatiska talet sχ( G ) i en graf G är det minsta k så att G är starkt k -färgbart. En graf är starkt k -kromatisk om den har ett starkt kromatiskt tal k .
Några egenskaper hos sχ( G ):
- sχ( G ) > Δ( G ).
- sχ( G ) ≤ 3 Δ( G ) − 1.
- Asymptotiskt, sχ( G ) ≤ 11 Δ( G ) / 4 + o(Δ( G )).
Här är Δ( G ) den maximala graden .
Stark kromatisk nummer introducerades oberoende av Alon (1988) och Fellows (1990).
Relaterade problem
Givet en graf och en partition av hörnen, är en oberoende transversal en uppsättning U av icke-angränsande hörn så att varje del innehåller exakt en vertex av U . En stark färgning är ekvivalent med en uppdelning av hörnen i disjunkta oberoende transversaler (varje oberoende transversal är en enda "färg"). Detta i motsats till graffärgning , som är en uppdelning av en grafs hörn i ett givet antal oberoende uppsättningar , utan kravet att dessa oberoende uppsättningar är tvärgående.
För att illustrera skillnaden mellan dessa begrepp, överväg en fakultet med flera institutioner, där dekanus vill konstruera en kommitté av fakultetsmedlemmar. Men vissa fakultetsmedlemmar är i konflikt och kommer inte att sitta i samma kommitté. Om "konflikt"-relationerna representeras av kanterna på en graf, då:
- En oberoende uppsättning är en kommitté utan konflikt.
- En oberoende transversal är en kommitté utan konflikt, med exakt en ledamot från varje avdelning.
- En graffärgning är en uppdelning av fakultetsmedlemmarna i kommittéer utan konflikt.
- En stark färgsättning är en uppdelning av fakultetsmedlemmarna i kommittéer utan konflikt och med exakt en ledamot från varje institution. Därför kallas detta problem ibland för den lyckliga dekanproblemet .