Article in volume

Authors:

M. Choi

Myungho Choi

Seoul National University

email: nums8080@snu.ac.kr

0000-0001-8921-1565

M. Kwak

Minki Kwak

Seoul National University

email: limpkmk@naver.com

S-R. Kim

Suh-Ryung Kim

Seoul National University

email: srkim@snu.ac.kr

Title:

The triangle-free graphs that are competition graphs of multipartite tournaments

Source:

Discussiones Mathematicae Graph Theory 45(1) (2025) 191-217

Received: 2023-03-25 , Revised: 2023-10-10 , Accepted: 2023-10-10 , Available online: 2023-11-07 , https://doi.org/10.7151/dmgt.2525

Abstract:

Keywords:

competition graph, triangle-free graph, multipartite tournament

References:

1. H.H. Cho, S-R. Kim and J.R. Lundgren, Domination graphs of regular tournaments, Discrete Math. 252 (2002) 57–71.
   https://doi.org/10.1016/S0012-365X(01)00289-8
2. J. Choi, S. Eoh, S-R. Kim and S. Lee, On $(1, 2)$-step competition graphs of bipartite tournaments, Discrete Appl. Math. 232 (2017) 107–115.
   https://doi.org/10.1016/j.dam.2017.08.004
3. M. Choi, M. Kwak and S-R. Kim, Competitively orientable complete multipartite graphs, Discrete Math. 345(9) (2022) 112950.
   https://doi.org/10.1016/j.disc.2022.112950
4. J.E. Cohen, Interval Graphs and Food Webs: a Finding and a Problem, Document 17696-PR (RAND Corporation, Santa Monica CA, 1968).
5. S. Eoh, J. Choi, S-R. Kim and M. Oh, The niche graphs of bipartite tournaments, Discrete Appl. Math. 282 (2020) 86–95.
   https://doi.org/10.1016/j.dam.2019.11.001
6. S. Eoh, S-R. Kim and H. Yoon, On m-step competition graphs of bipartite tournaments, Discrete Appl. Math. 283 (2020) 199–206.
   https://doi.org/10.1016/j.dam.2020.01.002
7. J.D. Factor, Domination graphs of extended rotational tournaments: chords and cycles, Ars Combin. 82 (2007) 69–82.
8. D.C. Fisher, J.R. Lundgren, D.R. Guichard, S.K. Merz and K.B. Reid, Domination graphs of tournaments with isolated vertices, Ars Combin. 66 (2003) 299–311.
9. D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, The domination and competition graphs of a tournament, J. Graph Theory 29 (1998) 103–110.
   https://doi.org/10.1002/(SICI)1097-0118(199810)29:2<103::AID-JGT6>3.0.CO;2-V
10. D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, Domination graphs of tournaments and digraphs, Congr. Numer. 108 (1995) 97–107.
11. S-R. Kim, The competition number and its variants, Ann. Discrete Math. 55 (1993) 313–326.
    https://doi.org/10.1016/S0167-5060(08)70396-0
12. S-R. Kim, J.Y. Lee, B. Park and Y. Sano, The competition graphs of oriented complete bipartite graphs, Discrete Appl. Math. 201 (2016) 182–190.
    https://doi.org/10.1016/j.dam.2015.07.021
13. J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in: Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, IMA Vol. Math. Appl. 17, F. Roberts (Ed(s)), (Springer, New York 1989) 221–243.
    https://doi.org/10.1007/978-1-4684-6381-1_9