Line graphs of directed graphs I

Document Type : Research Paper

Authors

1 Department of Mathematics and Statistics, Mississippi State University Mississippi State, MS 39762, USA

2 Department of Mathematics and Statistics, Wright State University Dayton, OH 45435, USA

Abstract

We determine the forbidden induced subgraphs for the intersection of the classes of chordal bipartite graphs and line graphs of acyclic directed graphs. This is a first step towards finding the forbidden induced subgraphs for the class of line graphs of directed graphs.

Keywords

Main Subjects


1] J. S. Bagga and Lowell W. Beineke, A survey of line digraphs and generalizations, Discrete Math. Lett., 6 (2021) 68–83.
[2] R. Behr, Edge coloring signed graphs, Discrete Math., 343 no. 2 (2020).
[3] L. W. Beineke, Characterizations of derived graphs, J. Combinatorial Theory, 9 (1970) 129–135.
[4] L. W. Beineke and J. S. Bagga, Line graphs and line digraphs, Developments in Mathematics, 68, Springer, Cham, [2021] ©2021, With a foreword by Gary Chartrand.
[5] L. W. Beineke and R. L. Hemminger, Infinite digraphs isomorphic with their line digraphs, J. Combinatorial Theory Ser. B, 21 no. 3 (1976) 245–256.
[6] K. Dabrowski, V. V. Lozin and Victor Zamaraev, On factorial properties of chordal bipartite graphs, Discrete Math., 312 no. 16 (2012) 2457–2465.
[7] M. Charles Golumbic and C. F. Goss, Perfect elimination and chordal bipartite graphs, J. Graph Theory, 2 no. 2 (1978) 155–163.
[8] F. Harary and R. Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo (2), 9 (1960) 161–168.
[9] J. Huang, Representation characterizations of chordal bipartite graphs, J. Combin. Theory Ser. B, 96 no. 5 (2006) 673–683.
  • Receive Date: 28 March 2023
  • Revise Date: 23 December 2023
  • Accept Date: 27 December 2023
  • Published Online: 20 January 2024