Decomposition of directed graphs and the Turán problem

DOI10.1007/S11253-014-0995-7zbMATH Open1308.05091arXiv1312.1544OpenAlexW2094163813MaRDI QIDQ2260873FDOQ2260873

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)

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.

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)

Cites Work

• Title not available (Why is that?)
• On graphs without a \(C_{4}\) or a diamond
• Title not available (Why is that?)
• Partial actions and automata

Cited In (3)

• Turán theorems and convexity invariants for directed graphs
• Topological Decomposition of Directed Graphs
• Turán function and \(H\)-decomposition problem for gem 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)