|
Сибирский математический журнал, 2011, том 52, номер 3, страницы 522–541
(Mi smj2217)
|
|
|
|
Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)
Ациклическая предписанная 5-раскрашиваемость плоских графов без 4-циклов
О. В. Бородинab, А. О. Ивановаc a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Новосибирский гос. университет, Новосибирск
c Институт математики при Якутском гос. университете,
Северо-Восточный федеральный университет, Якутск
Аннотация:
Гипотеза о предписанной ациклической 5-раскрашиваемости плоских графов (О. В. Бородин и др., 2002) пока что подтверждена лишь для некоторых узких классов графов: с обхватом не менее 5 (Монтасьер, Ошам и Распо, 2006), без 4- и 5-циклов, или без 4- и 6-циклов (Монтасьер, Ванг и Распо, 2007), без 4-циклов и хордальных 6-циклов (Занг и Кзу, 2009), без 4-циклов и 3-циклов на расстоянии менее 3 (Чен и Ванг, 2008), а также без 4-циклов и пересекающихся 3-циклов (Чен и Распо, 2010). Ванг и Чен (2009) доказали, что плоские графы без 4-циклов предписанно ациклически 6-раскрашиваемы. В работе доказано, что плоский граф без 4-циклов предписанно ациклически 5-раскрашиваем, что является совместным усилением всех вышеперечисленных результатов.
Ключевые слова:
граф, плоский граф, раскраска, ациклическая раскраска, предписанная раскраска.
Статья поступила: 18.07.2010
Образец цитирования:
О. В. Бородин, А. О. Иванова, “Ациклическая предписанная 5-раскрашиваемость плоских графов без 4-циклов”, Сиб. матем. журн., 52:3 (2011), 522–541; Siberian Math. J., 52:3 (2011), 411–425
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj2217 https://www.mathnet.ru/rus/smj/v52/i3/p522
|
Статистика просмотров: |
Страница аннотации: | 344 | PDF полного текста: | 68 | Список литературы: | 65 | Первая страница: | 11 |
|