On the Caccetta-Häggkvist conjecture with forbidden subgraphs
From MaRDI portal
Publication:2853341
DOI10.1002/JGT.21707zbMATH Open1273.05115arXiv1107.2247OpenAlexW2102204848WikidataQ123285630 ScholiaQ123285630MaRDI QIDQ2853341FDOQ2853341
Authors: Alexander Razborov 
Publication date: 21 October 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: The Caccetta-Haggkvist conjecture made in 1978 asserts that every orgraph on n vertices without oriented cycles of length <= l must contain a vertex of outdegree at most (n-1)/l. It has a rather elaborate set of (conjectured) extremal configurations. In this paper we consider the case l=3 that received quite a significant attention in the literature. We identify three orgraphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta-Haggkvist conjecture for orgraphs missing as induced subgraphs any of these orgraphs, along with cycles of length 3. Using a standard trick, we can also lift the restriction of being induced, although this makes graphs in our list slightly more complicated.
Full work available at URL: https://arxiv.org/abs/1107.2247
Recommendations
- The Lemmens-Seidel conjecture and forbidden subgraphs
- scientific article
- Forbidden subgraphs and the König-Egerváry property
- On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
- Forbidden subgraphs and forbidden substructures
- Forbidden subgraphs, stability and hamiltonicity
- Forbidden subgraphs and the Kőnig property
- The number of graphs with large forbidden subgraphs
- scientific article; zbMATH DE number 1185308
- Forbidden subgraphs and bounds on the size of a maximum matching
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Vertex degrees (05C07)
Cites Work
- Limits of dense graph sequences
- On 3-hypergraphs with forbidden 4-vertex configurations
- Flag algebras
- On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
- Title not available (Why is that?)
- Directed triangles in digraphs
- Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two
- Counting flags in triangle-free digraphs
- On the girth of digraphs
- Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
- Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
- On directed triangles in digraphs
- A note on minimal directed graphs with given girth
- Short cycles in digraphs
- On the Caccetta-Häggkvist conjecture
- A note on short cycles in digraphs
- Short cycles in directed graphs
- On minimal regular digraphs with given girth
Cited In (21)
- Counting flags in triangle-free digraphs
- A proof of Cunningham's conjecture on restricted subgraphs and jump systems
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
- An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem
- Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two
- On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
- Forbidden configurations for hypohamiltonian graphs
- Forbidden subgraphs and the König-Egerváry property
- The Lemmens-Seidel conjecture and forbidden subgraphs
- Minimum number of edges that occur in odd cycles
- Rainbow cycles for families of matchings
- Degree conditions forcing oriented cycles
- Note on upper bound graphs and forbidden subposets
- Decomposing and colouring some locally semicomplete digraphs
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- Properly colored short cycles in edge-colored graphs
- Sparse halves in dense triangle-free graphs
- Rainbow triangles in three-colored graphs
- On Turán's \((3,4)\)-problem with forbidden subgraphs
- Short rainbow cycles in graphs and matroids
- On the density of transitive tournaments
This page was built for publication: On the Caccetta-Häggkvist conjecture with forbidden subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2853341)
