Premium
On the Caccetta–Häggkvist Conjecture with Forbidden Subgraphs
Author(s) -
Razborov Alexander A.
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21707
Subject(s) - combinatorics , conjecture , mathematics , vertex (graph theory) , lift (data mining) , graph , induced subgraph , discrete mathematics , computer science , data mining
Abstract The Caccetta–Häggkvist conjecture developed in 1978 asserts that every oriented graph on n vertices without oriented cycles of length ≤ ℓ must contain a vertex of outdegree at mostn − 1 ℓ . It has a rather elaborate set of (conjectured) extremal configurations. In this paper, we consider the case ℓ = 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 withC ⃗ 3 . Using a standard method, we can also lift the restriction of being induced, though this makes graphs in our list slightly more complicated.