Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
David Wood
David Wood
  • 1.3k
  • 9
  • 12

There are triangle-free d$d$-degenerate graphs with chromatic number d+1;$d+1$; see http://dx.doi.org/10.1006/jctb.1999.1910 or http://dx.doi.org/10.1017/S0963548399004022 or https://arxiv.org/pdf/1310.2972.pdf. So I suspect that the desired characterisation is impossible.

There are triangle-free d-degenerate graphs with chromatic number d+1; see http://dx.doi.org/10.1017/S0963548399004022 or https://arxiv.org/pdf/1310.2972.pdf. So I suspect that the desired characterisation is impossible.

There are triangle-free $d$-degenerate graphs with chromatic number $d+1$; see http://dx.doi.org/10.1006/jctb.1999.1910 or http://dx.doi.org/10.1017/S0963548399004022 or https://arxiv.org/pdf/1310.2972.pdf. So I suspect that the desired characterisation is impossible.

Source Link
David Wood
David Wood
  • 1.3k
  • 9
  • 12

There are triangle-free d-degenerate graphs with chromatic number d+1; see http://dx.doi.org/10.1017/S0963548399004022 or https://arxiv.org/pdf/1310.2972.pdf. So I suspect that the desired characterisation is impossible.