RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Главная страница
О проекте
Программное обеспечение
Классификаторы
Полезные ссылки
Пользовательское
соглашение

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

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






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


J. Graph Theory, 2013, том 74, выпуск 2, страницы 236–248 (Mi jgt2)  

On the Caccetta–Häggkvist conjecture with forbidden subgraphs

A. Razborov

Department of Computer Science, University of Chicago Chicago, IL, USA

Аннотация: The Caccetta–Häggkvist conjecture developed in 1978 asserts that every oriented graph on $n$ vertices without oriented cycles of length $\leqslant \ell$ must contain a vertex of outdegree at most $\frac{n-1}{\ell}$. It has a rather elaborate set of (conjectured) extremal configurations. In this paper, we consider the case $\ell=3$ that received quite a significant attention in the literature. We identify three oriented graphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta–Häggkvist conjecture for oriented graphs missing as induced subgraphs any of these oriented graphs, along with $C_3$. Using a standard method, we can also lift the restriction of being induced, though this makes graphs in our list slightly more complicated.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований
Part of this work was done while the author was at Steklov Mathematical Institute, supported by the Russian Foundation for Basic Research, and at Toyota Technological Institute, Chicago.


DOI: https://doi.org/10.1002/jgt.21707


Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 26.07.2011
Язык публикации: английский

Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/jgt2

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:21

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018