Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 1, 2000, том 7, выпуск 3, страницы 72–85 (Mi da272)  

Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)

Об одном алгоритме раскраски ребер мультиграфов

В. А. Ташкинов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Пусть $n(G)$, $m(G)$, $\Delta(G)$ и $q(G)$ обозначают соответственно число вершин, число ребер, максимальную степень вершин и хроматический класс мультиграфа $G$. М. К. Гольдберг предположил, что существует эффективный алгоритм раскраски ребер произвольного мультиграфа $G$ в $\max\{q(G),\Delta(G)+1\}$ цветов. Он же предположил, что для любого мультиграфа $G$ с хроматическим классом $q(G)>\Delta(G)+1$ справедливо равенство
$$ q(G)=\max_{H\subseteq G}\lceil\frac{m(H)}{\lfloor\frac{n(H)}2\rfloor}\rceil. $$
Т. Нишизеки и К. Кашиваги доказали это равенство для мультиграфов с $q(G)>\frac{11\Delta(G)+8}{10}$ при помощи эффективного алгоритма раскраски ребер произвольного мультиграфа $G$ в $\max\{q(G),\lfloor\frac{11\Delta(G)+8}{10}\rfloor\}$ цветов. В данной статье строится простой эффективный алгоритм раскраски ребер произвольного мультиграфа, с помощью которого дается более короткое доказательство этих результатов. Библиогр. 7.

Полный текст: PDF файл (1632 kB)

Реферативные базы данных:
УДК: 519.174
Статья поступила: 19.04.2000

Образец цитирования: В. А. Ташкинов, “Об одном алгоритме раскраски ребер мультиграфов”, Дискретн. анализ и исслед. опер., сер. 1, 7:3 (2000), 72–85

Цитирование в формате AMSBIB
\RBibitem{Tas00}
\by В.~А.~Ташкинов
\paper Об одном алгоритме раскраски ребер мультиграфов
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2000
\vol 7
\issue 3
\pages 72--85
\mathnet{http://mi.mathnet.ru/da272}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1794647}
\zmath{https://zbmath.org/?q=an:0955.05036}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da272
  • http://mi.mathnet.ru/rus/da/v7/s1/i3/p72

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Goldberg M.K., “Clusters in a multigraph with elevated density”, Electron J Combin, 14:1 (2007), R10  mathscinet  zmath  isi
    2. Scheide D., Stiebitz M., “On Vizing's bound for the chromatic index of a multigraph”, Discrete Math, 309:15 (2009), 4920–4925  crossref  mathscinet  zmath  isi  scopus
    3. McDonald J.M., “Achieving maximum chromatic index in multigraphs”, Discrete Math, 309:8 (2009), 2077–2084  crossref  mathscinet  zmath  isi  scopus
    4. Scheide D., Stiebitz M., “Vizing's Coloring Algorithm and the Fan Number”, J Graph Theory, 65:2 (2010), 115–138  crossref  mathscinet  zmath  isi  scopus
    5. Scheide D., “Graph edge colouring: Tashkinov trees and Goldberg's conjecture”, Journal of Combinatorial Theory Series B, 100:1 (2010), 68–96  crossref  mathscinet  zmath  isi  scopus
    6. Chen G., Yu X., Zang W., “Approximating the chromatic index of multigraphs”, J Comb Optim, 21:2 (2011), 219–246  crossref  mathscinet  zmath  isi  scopus
    7. McDonald J.M., “On a Theorem of Goldberg”, J Graph Theory, 68:1 (2011), 8–21  crossref  mathscinet  zmath  isi  scopus
    8. Haxell P., McDonald J., “On characterizing Vizing's edge colouring bound”, J Graph Theory, 69:2 (2012), 160–168  crossref  mathscinet  zmath  isi  scopus
    9. Haxell P.E., Kierstead H.A., “Edge Coloring Multigraphs Without Small Dense Subsets”, Discrete Math., 338:12 (2015), 2502–2506  crossref  mathscinet  zmath  isi  scopus
    10. Chen G., Gao Yu., Kim R., Postle L., Shan S., “Chromatic Index Determined By Fractional Chromatic Index”, J. Comb. Theory Ser. B, 131 (2018), 85–108  crossref  mathscinet  zmath  isi  scopus
    11. Chen G., Jing G., “Structural Properties of Edge-Chromatic Critical Multigraphs”, J. Comb. Theory Ser. B, 139 (2019), 128–162  crossref  mathscinet  zmath  isi  scopus
    12. Haxell P., Krivelevich M., Kronenberg G., “Goldberg'S Conjecture Is True For Random Multigraphs”, J. Comb. Theory Ser. B, 138 (2019), 314–349  crossref  mathscinet  zmath  isi  scopus
    13. Chen X., Zang W., Zhao Q., “Densities, Matchings, and Fractional Edge-Colorings”, SIAM J. Optim., 29:1 (2019), 240–261  crossref  mathscinet  zmath  isi  scopus
    14. Cao Ya., Chen G., Jing G., Stiebitz M., Toft B., “Graph Edge Coloring: a Survey”, Graphs Comb., 35:1 (2019), 33–66  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:335
    Полный текст:144
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022