Ramsey-type results for path covers and path partitions. II: Digraphs

DOI10.1016/J.AMC.2023.128205MaRDI QIDQ6096342zbMATH OpenFDO

Authors Shuya Chiba, Michitaka Furuya

Publication date 12 September 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

digraphforbidden subdigraphpath cover numberpath partition numberRamsey number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Abstract: Recently, the authors gave Ramsey-type results for the path cover/partition number of graphs. In this paper, we continue the research about them focusing on digraphs, and find a relationship between the path cover/partition number and forbidden structures in digraphs. Let $D$ be a weakly connected digraph. A family $mathcalP$ of subdigraphs of $D$ is called a {it path cover} (resp. a {it path partition}) of $D$ if $$ (resp. $$) and every element of $mathcalP$ is a directed path. The minimum cardinality of a path cover (resp. a path partition) of $D$ is denoted by $mpc(D)$ (resp. $mpp(D)$). In this paper, we find forbidden structure conditions assuring us that $mpc(D)$ (or $mpp(D)$) is bounded by a constant.

Recommendations

• Ramsey-type results for path covers and path partitions
• scientific article; zbMATH DE number 202590
• scientific article; zbMATH DE number 3887733
• The Path Partition Conjecture is true for some generalizations of tournaments
• scientific article; zbMATH DE number 3948328

Cites work

• A Ramsey-type theorem for the matching number regarding connected graphs
• Berge's conjecture on directed path partitions -- a survey
• Characterizing forbidden pairs for hamiltonian properties
• Finding a Longest Path in a Complete Multipartite Digraph
• Forbidden induced subgraphs for bounded p-intersection number
• Forbidden subgraphs for constant domination number
• Forbidden triples and traceability: A characterization
• Graph theory
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 1185328 (Why is no real title available?)
• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• Long paths and cycles in oriented graphs
• Longest paths in digraphs
• New results on maximum induced matchings in bipartite graphs and beyond
• On degree sum conditions for directed path-factors with a specified number of paths
• Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach
• Ramsey-type results for path covers and path partitions
• Traceability in graphs with forbidden triples of subgraphs

Cited in

(3)

• Ramsey-type results for path covers and path partitions
• Ramsey numbers of path-matchings, covering designs, and 1-cores
• Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture

This page was built for publication: Ramsey-type results for path covers and path partitions. II: Digraphs

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