Question

Что такое верхня и нижня оценка хроматического числа? Объясните пожалуйста. Вот вобще не понимаю

Answer 1

Ну то есть есть некое хроматическое число для каждого конкретного графа, то есть характеристика, которую можно неким способом вычислить. Но по каким-то причинам (долго, сложно, нет ЭВМ под рукой) не хотим определять его напрямую. Зато есть доказанные задолго до нас теоремы, что для каких-то классов графов, к которым наш конкретный граф, к счастью, принадлежит, хроматическое число должно быть меньше такой-то величины (верхня оценка) и больше другой какой-то величины (нижня оценка) .