Talk:Strong coloring
 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Haxell's references[edit]
Someone who knows the specific papers should put the cited results due to Penny Haxell in the references section. Adking80 20:35, 1 August 2007 (UTC)
Strong Coloring Conjecture[edit]
In https://www.sciencedirect.com/science/article/pii/S0012365X96003007?via%3Dihub R. Yuster showed an example for graphs with degree Δ and and partitions of size 2Δ - 1 where there is no strong coloring with respect to this partition. He actually showed that with this partition there is not even one possible color. The accepted conjecture is that any graph is 2Δ strong colorable. Aharoni, Berger and Ziv proved that any chordal graph is 2Δ+1 strong colorable. — Preceding unsigned comment added by 79.176.86.190 (talk) 19:21, 26 March 2021 (UTC)