Decomposition of directed graphs and the Turán problem

DOI10.1007/S11253-014-0995-7MaRDI QIDQ2260873zbMATH OpenOpenAlexFDO

Authors G. N. Zholtkevich, B. V. Novikov, Lyudmyla Yu. Polyakova

Publication date 12 March 2015

Published in Ukrainian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1544

zbMATH Keywords

forbidden subgraphsvertex decompositions of digraphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20) Probabilistic models, generic numerical methods in probability and statistics (65C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We consider vertex decompositions of (di)graphs which appear in Automata Theory, and establish some their properties. Then we apply them to the problem of forbidden subgraphs.

Cites work

• scientific article; zbMATH DE number 3485226 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• On graphs without a \(C_{4}\) or a diamond
• Partial actions and automata

Cited in

(3)

• Turán function and \(H\)-decomposition problem for gem graphs
• Topological Decomposition of Directed Graphs
• Turán theorems and convexity invariants for directed graphs

This page was built for publication: Decomposition of directed graphs and the Turán problem

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