Подробное описание документа
Л. Е. Айрапетян
О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа / Л. Е. Айрапетян ; Российско-армянский (славянский) университет. - Ереван : б. и., 2020. -
Эффективность применения методов теории графов для исследования задач о расписаниях хорошо известна. Понятие интервальной раскраски ребер было впервые введено А.С. Асратяном и Р.Р. Камаляном в 1987 году, и было мотивированно проблемой поиска компактных школьных расписаний, т.е. не имеющих “окон”. Правильная раскраска графа G цветами 1, 2, ... t называется интервальной t – раскраской, если для любой вершины v ∈ V(G), инцидентные ей ребра раскрашены последовательными цветами, и любым цветом i (1 ≤ i ≤ t) раскрашено хотя бы одно ребро графа G. Они доказали, что если G является интервально раскрашиваемым, то χ(G) = Δ(G). Кроме того, если граф G является г – регулярным, то граф G имеет интервальную раскраску тогда и только тогда, когда граф G имеет правильную г -раскраску. Это означает, что задача “Является ли данный r – регулярный (r ≥3) граф интервально раскрашиваемым графом или нет?” является NP -полной задачей. А.С. Асратян и Р.Р. Камалян также доказали, что если граф без треугольников G имеет интервальную t - раскраску, тогда t ≤ |V(G)| - 1. Р.Р. Камаляном исследованы интервальные раскраски полных двудольных графов и деревьев. В частности, он доказал, что полный двудольный граф Km,n имеет интервальную t - раскраску тогда и только тогда, когда m + n - (m, n) ≤ t ≤ m + n - 1, где (m, n) - наибольший общий делитель чисел m и n. П.А. Петросян исследовал интервальные раскраски полных графов и n – мерных кубов. В частности, он доказал, что если
