Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета. Формально...

Интервальное хроматическое число X<(H) упорядоченного графа[англ.] H — это минимальное число интервалов, на которое может быть разбит (линейно упорядоченный)...

Наименьшее число цветов, необходимое для рёберной раскраски графа G {\displaystyle G}  — это его хроматический индекс, или рёберное хроматическое число, χ ′...

\mathbb {R} ^{3}} сделать это, не создав самопересечения, невозможно. Хроматическое число поверхности равно 6. Если разрезать бутылку Клейна пополам по её...

в палатальный [ç]. Хиазм. Распределение хи-квадрат в статистике. Хроматическое число в теории графов. Эйлерова характеристика в топологии. Диэлектрическая...

решить задачу для всех конечных подмножеств точек. Очевидно, что хроматическое число одномерного пространства равно двум, однако уже для плоскости ответ...

Опубликовали его Бринкман и Мерингер в 1997 году. Граф имеет хроматическое число 4, хроматический индекс 5, радиус 3, диаметр 3 и обхват 5. Он также вершинно...

описаны Вагнером. Графы с любым конечным числом Хадвигера разрежены и имеют малое хроматическое число. Определение числа Хадвигера для графа является NP-трудной...

40 рёбрами. Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Он также является...

ориентированного хроматического числа неориентированного графа как максимального хроматического числа из всех его ориентаций. Ориентированное хроматическое число ориентированного...

Грюнбаумом. Звёздное хроматическое число χ s ( G ) {\displaystyle \chi _{s}(G)} графа G {\displaystyle G}  — это минимальное число цветов, необходимых...

(вложение показано ниже). Граф является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 3, диаметр 3 и обхват 4. Он является также...

степенью Δ хроматическое число графа G не больше Δ, за исключением случаев, когда G — клика или нечётный цикл. В этих случаях хроматическое число равно Δ + 1...

Доматическое число — это максимальное число таких множеств. Раскраска вершин Разбиение вершин на непересекающиеся независимые множества. Хроматическое число является...

треугольника с двумя непересекающимися висячими рёбрами. Хроматическое число графа равно 3, хроматический индекс равен 3, радиус 2, диаметр 3 и обхват 3. Граф...

использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога. Пусть G и H — два...

хроматическом числе. Более того, хроматическое число является наименьшим положительным целым, при котором хроматический многочлен не обращается в нуль,...

цветов. b-кратное хроматическое число χb(G) — это наименьшее a, при котором существует a:b-раскраска. Дробным хроматическим числом χf(‘‘G’’) называется...

вершин. Минимальное число цветов k, требующихся для получения (k, d)-раскраски графа G, называется d-дефектным хроматическим числом, χ d ( G ) {\displaystyle...

могут быть использованы для T-раскраски графа G. T-хроматическое число равно хроматическому числу, χ T ( G ) = χ ( G ) {\displaystyle \chi _{T}(G)=\chi...

(G)} . В этом смысле мы говорим, что цикловое хроматичеcкое число уточняет обычное хроматическое число. Цикловую раскраску первоначально определил Винс...

{\displaystyle g} , и при этом хроматическое число G как минимум на k {\displaystyle k} . Зафиксируем большое целое число n {\displaystyle n} . Рассмотрим...

{\displaystyle K_{4}} рёберно раскрашен в 5 цветов Хроматический индекс графа, или рёберное хроматическое число графа, или рёберная k-хроматичность, — это минимальное...

покрасить в один цвет. Исходя из некоторой модификации принципа Дирихле, хроматическое число графа можно оценить как χ ( G ) ≥ | V | α ( G ) {\displaystyle \chi...

математике. Число Хадвигера и хроматическое число являются инвариантами графа при перенумерации его вершин. Инвариант эллиптической кривой — число J ( E )...

инцидентно ровно три ребра. k-дольный граф — граф G, у которого хроматическое число c(G)=k k-связный граф — связный граф, в котором не существует набора...

фиксировано, задача становится NP-полной. Любой верхушечный граф имеет хроматическое число, не превосходящее пяти — планарный граф без верхушки требует не более...

является двудольным тогда и только тогда, когда он 2-хроматический; то есть его хроматическое число равняется двум. Граф разбивается на пары разноцветных...

доказательство использует окружности. Обозначим через n хроматическое число графа G и назначим целые числа ( 1.. n ) {\displaystyle (1..n)} для n цветов. В 2...

Николаасом де Брёйном. Хроматическое число бесконечного графа, если это число конечно, равно наибольшему хроматическому числу среди всех его конечных...

темперации могут также делить иной интервал, не только октаву, на целое число равных ступеней. Чтобы избежать неясности, в англоязычной литературе, например...