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

10.22108/toc.2023.137205.2057

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.

Articles in Press, Corrected Proof
Available Online from 20 January 2024
  • Receive Date: 28 March 2023
  • Revise Date: 23 December 2023
  • Accept Date: 27 December 2023
  • Published Online: 20 January 2024