Structure of (bull, diamond)-free graphs and its applications

2021/07/08 by Suchismita Mishra, Mishra, Suchismita
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2107.03750

Abstract

This paper discusses the complete structure of the (bull, diamond)-free graphs. As an application of that, we give the characterization of the partitionable (bull, diamond)-free graphs. Moreover, we show that such a partition for a partitionable (bull, diamond)-free graph can be found in polynomial time. Additionally, we show that the cop number of a (bull, diamond)-free graph containing a triangle is at most two less than its diameter. Furthermore, the cop number of a connected (P_n, bull, diamond)-free graph with a triangle, is at most n-3, for any natural number n>3. We also discuss a couple of applications of the structural theorem of the (bull, diamond)-free graphs in the conclusions.

Citations

• Vertex-to-vertex pursuit in a graph

Related

• Structural description of (bull, house)-free graphs
• On the structure of (claw,bull)-free graphs
• Structure and coloring of some (P₇,C₄)-free graphs
• Cops and robbers on 2K₂-free graphs
• On graphs without a C4 or a diamond