Pith. sign in

REVIEW 2 major objections 4 minor 13 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every triangle-free competition graph of a multipartite tournament is on a short, explicit list.

desk verdict Complete triangle-free classification for multipartite competition graphs, solidly argued, with the main caveat being a quoted external theorem for the bipartite path-union case. read the letter →

arxiv 2009.09881 v2 pith:P2V76HZ3 submitted 2020-09-21 math.CO

Myungho Choi , Minki Kwak , Suh-Ryung Kim This is my paper · ORCID
classification math.CO MSC 05C2005C75
keywords competitiongraphmultipartitetournamenttriangle-freeorientationclassificationpathandcycleunionsindegreeboundk-partite
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper determines exactly which triangle-free graphs can arise as competition graphs of multipartite tournaments. In a competition graph, two vertices are joined when they share a common out-neighbor in the underlying directed graph, and a k-partite tournament is an orientation of a complete k-partite graph. The authors prove that a connected triangle-free graph occurs only for $k = 3, 4$, or $5$, and then give the explicit finite list of six, three, and one graphs respectively. For disconnected triangle-free graphs the only possible values are $k = 2, 3$, or $4$, again with explicit finite lists. The classification shows that this natural family is surprisingly small: aside from isolated-vertex decorations, only certain paths, one star, $C_5$, $C_6$, $C_4 \cup C_4$, and a few small trees appear.

What carries the argument

The engine of the classification is a counting bound: if a competition graph is triangle-free, then every vertex of the tournament has indegree at most $2$, because all in-neighbors of a vertex share that vertex as a common out-neighbor and would otherwise form a triangle. Counting arcs gives $|E(G)| \le |A(D)|/2 \le |V(D)|$, and combining this with the exact arc count of a complete multipartite graph forces the partite-set sizes into a few small shapes, enumerated in Lemmas 2.4 and 2.17. The same indegree bound makes the competition graph very sparse, so the remaining work is to identify which small paths, cycles, stars, and trees admit suitable orientations.

What would settle it

Because the classification lists are finite and explicit, one concrete disproof would be to exhibit an orientation of a complete multipartite graph whose triangle-free competition graph is not on the listed sets—for example, a disconnected one containing $P_5 \cup P_3$ or a connected one outside the ten named graphs; exhaustive search over orientations of $K_{n_1,n_2}$ and $K_{n_1,n_2,n_3}$ for small $n_i$ would settle whether such an example exists.

Watch

Extended reading notes

Core claim

The paper's central discovery is a complete dichotomy for triangle-free graphs $G$. If $G$ is connected, it is the competition graph of a $k$-partite tournament for some $k \ge 2$ exactly when $k \in \{3,4,5\}$ and $G$ is one of $\{G_1,G_2,G_3,G_4,P_6,C_6\}$ for $k=3$, one of $\{P_5,K_{1,3},G_2\}$ for $k=4$, or $C_5$ for $k=5$. If $G$ is disconnected, the same holds exactly when $k \in \{2,3,4\}$, with the explicit lists of Theorems 3.4, 3.9, and 3.10: bipartite tournaments give ten disjoint-union forms such as empty graphs, $P_2$ with isolated vertices, $P_3 \cup P_3$, $P_4 \cup P_3$, $C_4 \cup C_4$, and $P_2 \cup P_2 \cup P_2 \cup P_2$; $4$-partite tournaments give only $P_3 \cup P_2$ and $P_3 \cup I_1$; tripartite tournaments give ten forms including $K_{1,3} \cup P_2$ and $P_2 \cup P_2 \cup P_2$. Thus every other triangle-free graph is excluded for all $k \ge 2$.

Load-bearing premise

The bipartite half of the classification relies on a cited theorem that $P_m \cup P_n$ is the competition graph of a bipartite tournament only for $(m,n) = (1,1), (2,1), (3,3), (4,3)$; if that list ever gains another case, Theorem 3.4's list would change.

Editorial extensions

If this is right

  • For every $k \ge 6$, no $k$-partite tournament has a triangle-free competition graph; every such competition graph contains a triangle.
  • The connected triangle-free competition graphs are exactly the six $3$-partite graphs $\{G_1,G_2,G_3,G_4,P_6,C_6\}$, the three $4$-partite graphs $\{P_5,K_{1,3},G_2\}$, and $C_5$; no other connected triangle-free graph can appear for any $k$.
  • The disconnected triangle-free competition graphs are exactly the listed disjoint unions of paths, with optional isolated vertices, together with $C_4 \cup C_4$ and the listed star-plus-path forms; in particular, no disconnected triangle-free graph has a cycle component other than $C_4$.
  • The theorem pins down which values of $k$ can occur for each triangle-free graph, and the lists are small enough to check any candidate graph directly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A likely extension is that the same indegree counting should generalize from triangle-free graphs to $K_{r+1}$-free competition graphs, where every vertex would have indegree at most $r$, yielding analogous partite-size inequalities and possibly finite classifications for each fixed $r$.
  • Because the lists are finite and explicit, the classification could be converted into a recognition algorithm: check a triangle-free graph against the named graphs and, for a candidate, search only the few possible orientations rather than all tournaments.
  • The paper's own closing suggestion points to cubic graphs as a natural next test case; the sparsity mechanism used here may or may not survive once vertices can have degree $3$, so cubic graphs would be a good probe of how far the classification reaches.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The paper's central discovery is a complete dichotomy for triangle-free graphs $G$. If $G$ is connected, it is the competition graph of a $k$-partite tournament for some $k \ge 2$ exactly when $k \in \{3,4,5\}$ and $G$ is one of $\{G_1,G_2,G_3,G_4,P_6,C_6\}$ for $k=3$, one of $\{P_5,K_{1,3},G_2\}$ for $k=4$, or $C_5$ for $k=5$. If $G$ is disconnected, the same holds exactly when $k \in \{2,3,4\}$,

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper classifies all triangle-free graphs that arise as competition graphs of multipartite tournaments. The main connected result is that a connected triangle-free graph has this property for some k≥2 exactly when k∈{3,4,5}, with complete lists: {G1,G2,G3,G4,P6,C6} for k=3, {P5,K1,3,G2} for k=4, and {C5} for k=5 (Theorem 2.19). For disconnected triangle-free graphs the paper proves that k must be 2, 3, or 4 and gives complete lists in Theorems 3.4, 3.9, and 3.10. The proofs combine a degree bound forced by triangle-freeness (Lemma 2.2) with structural lemmas restricting possible partite-set sizes, followed by case analyses and explicit orientations of multipartite tournaments realizing each listed graph.

Significance. If correct, the paper settles the triangle-free case of a natural classification problem and complements the authors' earlier work on complete competition graphs of multipartite tournaments. The lists are concrete, and the sufficiency directions are supported by explicit digraph constructions, which makes the classification easy to check and use. The paper also relies appropriately on known results for tournaments and bipartite tournaments; I see no circularity, since the authors' previous paper [3] is used only as motivation and not as a proof dependency. The main value is the complete and relatively clean decomposition of the problem into the cases k=2,3,4,5 with a small number of exceptional graphs.

major comments (2)
  1. [§2, Lemma 2.7] The inference 'Therefore d+(u)=3 or 4. Thus u is incident to at least three edges in C(T)' is too terse and is not justified as written. Since the four vertices other than u have indegree 2, each out-neighbor w of u has exactly one additional in-neighbor, so each such w gives an edge incident to u; however, different out-neighbors could in principle contribute the same neighbor of u, and the proof does not rule this out. This step is load-bearing because it is the only argument excluding P5 from the tripartite list, so the distinctness of the resulting edges needs to be made explicit.
  2. [§3.1, Proposition 3.2 and Theorem 3.4] Proposition 3.2 is cited from [12] and is the sole reason that P3∪P3 is admitted and that path-pair unions beyond (4,3) are excluded in Theorem 3.4. Since a misstatement of this external result would change the bipartite list, the authors should either include a short verification of the path-pair cases or give a precise pointer to the exact theorem and proof location in [12]. I do not regard reliance on a published theorem as circular or as an internal inconsistency, but the exact statement is load-bearing and should be checked carefully.
minor comments (4)
  1. [§2, Lemma 2.15] The word 'regualr' should be 'regular'.
  2. [§2, Theorem 2.19 proof] The graph called 'G5' in the k=4 case is not defined; it should be 'G2' from Figure 3, both in the sentence 'C(D) is isomorphic to P5 or G5' and in the sentence 'C(D7) ∼= G5'.
  3. [§1, Introduction] The sentence beginning 'we show that a connected triangle-free graph...' starts with a lowercase 'we' after a period; it should be capitalized.
  4. [§3.1, Theorem 3.4 proof] In the 'if' part, the constructions for P4∪P3 and P3∪P2∪P2 are said to have been 'constructed in the subcase 3-2', which is part of the 'only if' proof; a brief forward reference or restatement would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the classifications are obtained by direct case analysis and explicit constructions, with all borrowed theorems cited as independent external results.

full rationale

The paper's derivation chain is not circular. The main theorems (2.19, 3.4, 3.9, 3.10) are proved by case analyses on partite-set sizes, using elementary lemmas derived from the definition of competition graph and from triangle-freeness, and each listed graph is realized by an explicitly constructed multipartite tournament. The "only if" directions are exclusion arguments based on degree sums, indegree bounds, and component-structure reasoning; the "if" directions are witness constructions. No fitted parameter is later renamed as a prediction, and no object is defined in terms of the classification it is supposed to establish. The paper does rely on external published theorems, notably Proposition 2.12 (Fisher), Propositions 2.13 and 2.14 (Fisher and Cho), and Propositions 2.18, 3.2, and 3.3 (Kim et al.). These are parameter-free statements about tournaments and bipartite tournaments; none of them assumes the triangle-free classification being proved. Proposition 3.2 is load-bearing for Theorem 3.4, but it is cited as an independent result with its own proof in the literature, not as an unverified assertion of this paper. The fact that one current author also appears on the cited paper does not make the citation circular, since the cited result is independent support rather than a restatement of the target theorem. The self-citation [3] in the introduction and closing remarks is motivational only and is not used as a proof dependency. Any concern about whether Proposition 3.2 is correctly quoted or fully correct is a correctness risk, not a circularity defect.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The proofs rely on five external theorems from the cited literature, all parameter-free published results. They are used as black boxes but not derived in this paper.

assumptions (5)
  • standard math Proposition 2.12 (Fisher): the minimum possible number of edges in the competition graph of an n-tournament is C(n,2)-n.
    Used in Lemma 2.15 and Theorem 3.9 to lower-bound edge counts in 5- and 4-vertex tournament competition graphs.
  • standard math Proposition 2.13 (Fisher): a path on four or more vertices is not the complement of the competition graph of a tournament.
    Used in Theorem 2.19 to exclude a path graph in the k=4, n1=n2=n3=n4=1 case.
  • standard math Proposition 2.18 (Kim et al.): the competition graph of an orientation of a bipartite graph has no edges between the two parts.
    Used in Theorem 2.19 to rule out connected graphs from k=2 bipartite tournaments.
  • standard math Proposition 3.2 (Kim et al.): Pm union Pn is the competition graph of a bipartite tournament iff (m,n) is one of (1,1), (2,1), (3,3), or (4,3).
    Load-bearing for Theorem 3.4, determining which disjoint path pairs appear in the bipartite classification.
  • standard math Proposition 3.3 (Kim et al.): Cm union Cn is the competition graph of a bipartite tournament iff (m,n)=(4,4).
    Used in Theorem 3.4 to include C4 union C4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The triangle-free graphs which are competition graphs of multipartite tournaments." pith.science (2026). https://pith.science/paper/P2V76HZ3

@misc{pith2026200909881,
  author       = {Pith},
  title        = {Pith review of: The triangle-free graphs which are competition graphs of multipartite tournaments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P2V76HZ3}},
  note         = {Machine review of arXiv:2009.09881}
}
read the original abstract

In this paper, we discover all the triangle-free graphs that are competition graphs of multipartite tournaments.

Figures

Figures reproduced from arXiv: 2009.09881 by the authors.

Figure 1
Figure 1. A digraph D which is an orientation of K2,2,2 and whose competition graph is isomorphic to C6 The following lemma is an immediate consequence of Lemma 2.4. Lemma 2.5. For a connected triangle-free graph G of order n, if G is the competition graph of a tripartite tournament, then n ∈ {5, 6}. Lemma 2.6. For a positive integer n ≥ 3, a cycle Cn of length n is the competition graph of a tripartite tournament if and only… view at source ↗
Figure 2
Figure 2. A digraph D which is an orientation of K3,2,1 and whose competition graph is isomorphic to P6 C(T) is triangle-free, d −(v) ≤ 2 for each v ∈ V (T). Since there are four edges in C(T), there are four vertices of indegree 2 in T. Since |A(T)| = 8 and n = 5, there exists exactly one vertex of indegree 0 in T. Let u be the vertex of indegree 0 in T. If V3 = {u}, then N +(u) = V1 ∪ V2. Otherwise, either N +(u) = V2 ∪ V3 … view at source ↗
Figure 3
Figure 3. Connected triangle-free graphs mentioned in Lemma 2.9 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Two digraphs D1 and D2 which are orientations of K2,2,1 and whose competition graphs are isomorphic to G1 and G2, respectively D3 D4 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Two digraphs D3 and D4 which are orientations of K3,2,1 and whose competition graphs are isomorphic to G3 and G4, respectively 6 [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: A graph considered in the proof of Lemma 2.9 [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: A regular 5-tournament Proposition 2.14. (Cho [1]) If T is a regular n-tournament (n ≥ 3), then the complement of the competition graph of T is either an odd cycle or a forest of two or more paths. Lemma 2.15. If the competition graph C(D) of a 5-partite tournament D i…
Figure 8
Figure 8. Figure 8: Three digraphs D5, D6, and D7 which are orientations of K1,1,1,1, K2,1,1,1, and K2,1,1,1, respectively, and whose competition graphs are isomorphic to K1,3, P5, and G5, respectively the following holds: (a) n2 = 1; (b) n2 = 2; (c) n1 ≤ 6 and n2 = 3; (d) n1 = 4 and n2 =…
Figure 9
Figure 9. Figure 9: Digraphs D′ and D′′ in the proof of Theorem 3.4. for each vertex v in D. To reach a contradiction, we suppose that G has at least three isolated vertices. Then at least two isolated vertices belong to the same partite set in D. Without loss of generality, we may assume…
Figure 10
Figure 10. Figure 10: Bipartite tournaments in the proof of Theorem 3.4 [PITH_FULL_IMAGE:figures/full_fig_p017_10.png]
Figure 11
Figure 11. Figure 11: The digraphs D15 and D16 in the proof of Theorem 3.9 Lemma 2.2. Therefore |E(C(D))| = 2 or 3. Thus C(D) has exactly two components and so is isomorphic to I1 ∪ P3 or P2 ∪ P2. If C(D) is isomorphic to P2 ∪ P2, then D has two vertices a and b such that d −(a) = d −(b) =…
Figure 12
Figure 12. Figure 12: The digraphs in the proof of Theorem 3.10 [PITH_FULL_IMAGE:figures/full_fig_p024_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [3]

    Competitively orientable complete multipartite graphs

    Myungho Choi, Minki Kwak, and Suh-Ryung Kim. Multipartite tourn aments whose competition graphs are complete. arXiv preprint arXiv:2006.11743 , 2020

    work page Pith review arXiv 2006

  2. [12]

    T he competition graphs of oriented complete bipartite graphs

    Suh-Ryung Kim, Jung Yeun Lee, Boram Park, and Yoshio Sano. T he competition graphs of oriented complete bipartite graphs. Discrete Applied Mathematics, 201:182– 190, 2016

    work page 2016

  3. [1]

    Dominatio n graphs of regular tournaments

    Han Hyuk Cho, Suh-Ryung Kim, and J Richard Lundgren. Dominatio n graphs of regular tournaments. Discrete Mathematics , 252(1-3):57–71, 2002

    work page 2002

  4. [2]

    On (1 , 2)-step compe- tition graphs of bipartite tournaments

    Jihoon Choi, Soogang Eoh, Suh-Ryung Kim, and Sojung Lee. On (1 , 2)-step compe- tition graphs of bipartite tournaments. Discrete Applied Mathematics , 232:107–115, 2017

    work page 2017

  5. [4]

    Interval graphs and food webs: a finding and a pr oblem

    Joel E Cohen. Interval graphs and food webs: a finding and a pr oblem. RAND Corporation Document, 17696, 1968

    work page 1968

  6. [5]

    The niche g raphs of bipartite tournaments

    Soogang Eoh, Jihoon Choi, Suh-Ryung Kim, and Miok Oh. The niche g raphs of bipartite tournaments. Discrete Applied Mathematics , 2019

    work page 2019

  7. [6]

    On m-step comp etition graphs of bipartite tournaments

    Soogang Eoh, Suh-Ryung Kim, and Hyesun Yoon. On m-step comp etition graphs of bipartite tournaments. Discrete Applied Mathematics , 2020

    work page 2020

  8. [7]

    Domination graphs of extended rotational tou rnaments: chords and cycles

    James D Factor. Domination graphs of extended rotational tou rnaments: chords and cycles. Ars Combinatoria , 82:69–82, 2007

    work page 2007

Show all 13 references
  1. [8]

    Domination graphs of tournaments with isolated vertices

    David C Fisher, J Richard Lundgren, David R Guichard, Sarah K Mer z, and K Brooks Reid. Domination graphs of tournaments with isolated vertices. Ars Combinatoria , 66:299–311, 2003

    2003

  2. [9]

    The domination and competition graphs of a tournament

    David C Fisher, J Richard Lundgren, Sarah K Merz, and K Brooks R eid. The domination and competition graphs of a tournament. Journal of Graph Theory , 29(2):103–110, 1998. 25

    1998

  3. [10]

    D omination graphs of tournaments and digraphs

    David C Fisher, J Richard Lundgren, Sarah K Merz, and KB Reid. D omination graphs of tournaments and digraphs. Congressus Numerantium, pages 97–108, 1995

    1995

  4. [11]

    The competition number and its variants

    Suh-Ryung Kim. The competition number and its variants. In Annals of Discrete Mathematics, volume 55, pages 313–326. Elsevier, 1993

    1993

  5. [13]

    Food webs, competition graphs, competit ion-common enemy graphs, and niche graphs

    J Richard Lundgren. Food webs, competition graphs, competit ion-common enemy graphs, and niche graphs. In Applications of Combinatorics and Graph Theory to the Biological and Social Sciences , pages 221–243. Springer, 1989. 26

    1989

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.