RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Main page
About this project
Software
Classifications
Links
Terms of Use

Search papers
Search references

RSS
Current issues
Archive issues
What is RSS






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


J. Graph Theory, 2013, Volume 74, Issue 2, Pages 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

Abstract: 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.

Funding Agency Grant Number
Russian Foundation for Basic Research
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


Bibliographic databases:

Received: 26.07.2011
Accepted:29.08.2012
Language:

Linking options:
  • http://mi.mathnet.ru/eng/jgt2

    SHARE: 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
  • Number of views:
    This page:43

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020