What do you call a $k$-chromatic graph that’s $k+1$-chromatic if you add any arbitrary edge?

29 Views Asked by At

Is there an existing term for this? I imagine it’d be something like “maximally k-chromatic”.

2

There are 2 best solutions below

0
On BEST ANSWER

A complete $k$-partite graph.

1
On

If there is such a term, I would imagine "maximally $k$-chromatic" would be it. However, it would be best to explicitly define "maximally $k$-chromatic" as you did here, so there is no confusion.