Forbidden tournaments and the orientation completion problem

DOI10.1137/23M1604849MaRDI QIDQ6668354zbMATH OpenFDO

Authors Manuel Bodirsky, Santiago Guzmán-Pro

Publication date 22 January 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1604849

zbMATH Keywords

computational complexityhomomorphismsinfinite graphsorientations with forbidden patterns

Mathematics Subject Classification ID

Applications of model theory (03C98) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Infinite graphs (05C63) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Completing orientations of partially oriented graphs
• The number of oriantations having no fixed tournament
• Obstructions for acyclic local tournament orientation completions
• Counting H-free orientations of graphs
• Feedback arc set in bipartite tournaments is NP-complete

Cites work

• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• A dichotomy for first-order reducts of unary structures
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• A proof of the CSP dichotomy conjecture
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• ASNP: a tame fragment of existential second-order logic
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Completing orientations of partially oriented graphs
• Complexity of infinite-domain constraint satisfaction
• Constraint Satisfaction with Countable Homogeneous Templates
• Constraints, MMSNP and expander relational structures
• CORES OVER RAMSEY STRUCTURES
• Describing hereditary properties by forbidden circular orderings
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• In-tournament digraphs
• Minimal functions on the random graph
• Nombre chromatique et plus longs chemins d'un graphe
• On the computational complexity of ordered subgraph recognition
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• PROJECTIVE CLONE HOMOMORPHISMS
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The wonderland of reflections
• Two-element structures modulo primitive positive constructability
• Zur algebraischen Begründung der Graphentheorie. I

Cited in

(2)

• An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
• GMSNP and finite structures

This page was built for publication: Forbidden tournaments and the orientation completion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6668354)