pith. sign in

arxiv: 2411.07000 · v1 · submitted 2024-11-11 · 🧮 math.CO

Distinguishing chromatic number of middle and subdivision graphs

Amitayu Banerjee , Alexa Gopaulsingh , Zal\'an Moln\'ar This is my paper

Pith reviewed 2026-05-23 17:39 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C15
keywords distinguishing chromatic numbermiddle graphsubdivision graphdistinguishing numbertotal distinguishing numbermaximum degreegraph automorphism
0
0 comments X

The pith

The distinguishing chromatic number of the middle graph M(G) is Δ(G)+1 except for C4, K4, C6 and K3,3 where it equals Δ(G)+2.

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

The paper determines the distinguishing chromatic number of middle graphs M(G) for connected graphs G with at least three vertices by applying earlier theorems on distinguishing numbers. It finds this number equals the maximum degree plus one, except for the graphs C4, K4, C6 and K3,3 where it is two more than the maximum degree. The work also equates the distinguishing number of subdivision graphs S(G) to the total distinguishing number D''(G) of G and gives a sharp upper bound on the distinguishing chromatic number of S(G) in terms of the distinguishing number of G.

Core claim

Applying a result of Hamada and Yoshimura from 1976 and recent results of Alikhani and Soltani (2020) and Kalinowski and Pilsniak (2015), the distinguishing chromatic number χ_D(M(G)) of the middle graph M(G) is Δ(G)+1 except for four small graphs C4, K4, C6, and K3,3, and Δ(G)+2 otherwise. The distinguishing number D(S(G)) of the subdivision graph S(G) equals D''(G), so it is at most ⌈√Δ(G)⌉. A sharp upper bound is obtained for the distinguishing chromatic number of S(G) in terms of the distinguishing number of G.

What carries the argument

Direct application of prior results on distinguishing numbers and chromatic numbers to compute χ_D(M(G)) and relate D(S(G)) to D''(G).

Load-bearing premise

That the result of Hamada and Yoshimura from 1976 and the recent results of Alikhani and Soltani (2020) and Kalinowski and Pilsniak (2015) can be applied directly to determine χ_D(M(G)) for all simple finite connected graphs G with n ≥ 3.

What would settle it

A connected graph G with n ≥ 3 outside the four exceptions where χ_D(M(G)) is neither Δ(G)+1 nor Δ(G)+2, or where D(S(G)) is not equal to D''(G).

Figures

Figures reproduced from arXiv: 2411.07000 by Alexa Gopaulsingh, Amitayu Banerjee, Zal\'an Moln\'ar.

Figure 1
Figure 1. Figure 1: Graphs Q, L(Q), C+ 6 , K+ 3,3 , C + 4 , and K+ 4 . Lemma 2.4. If ψ ∈ Aut(G+) such that ψ(u) = u for all u ∈ V (G), then ψ = idG+ . Proof. Let up ∈ V (G+)\V (G). If ψ(up) = uq for some uq ∈ V (G+)\(V (G) ∪ {up}), then ψ(vp) = vq since automorphisms preserve adjacency, which is a contradiction to the given assumption. Lemma 2.5. If G ∈ {C4, C6, K4, K3,3}, then χ ′ D(G+) = ∆(G) + 2 [PITH_FULL_IMAGE:figures/f… view at source ↗
Figure 2
Figure 2. Figure 2: Graph G+. Let NG(vi) = {a1, ..., a∆(G)} be the open neighborhood of vi in G. Since all vertices of G have the same degree, i.e., ∆(G), we have f(πα(e)) = f(e) for the following reasons (see [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An edge coloring c : E(K+ 3,3 ) → {1, ..., ∆(K3,3) + 2} of K+ 3,3 . Now, ψ fixes all the vertices of G since for any zp, zq ∈ V (G)\{z1, z2} such that zp 6= zq, the length of Pz1,z2,zp is different than the length of Pz1,z2,zq . By Lemma 2.4, we have ψ = idG+ . This concludes the proof of the present Lemma. Theorem 2.8. If G is a connected graph of order n ≥ 3. Then χD(M(G)) = ∆(G) + 1 if G 6∈ {C4, K4, C6,… view at source ↗
Figure 4
Figure 4. Figure 4: Graphs S(G) and G. Since α is a g-preserving automorphism of G, we have the following: (1) For all v ∈ V (G), we have g(α(v)) = g(v) =⇒ f(α(v)) = f(v) =⇒ f(πα(v)) = f(v). (2) If {x, y} ∈ V (S(G))\V (G) and NS(G)(a) is the open neighborhood of a ∈ V (S(G)), then α({x, y}) ∈ NS(G)(α(x)) ∩ NS(G)(α(y)), since automorphisms preserve adjacency. Thus, {α(x), α(y)} = α({x, y}) since G is a simple graph (see [PITH… view at source ↗
read the original abstract

Let $G$ be a simple finite connected graph of order $n$ greater than or equal to $3$. We obtain the following results: (1). We apply a result of Hamada and Yoshimura from 1976 and some recent results of Alikhani and Soltani (2020) and Kalinowski and Pilsniak (2015) to determine the distinguishing chromatic number of the middle graph $M(G)$ of the graph $G$. In particular, the distinguishing chromatic number $\chi_{D}(M(G))$ of the middle graph $M(G)$ of the graph $G$ is $\Delta(G)+1$ except for four small graphs $C_{4}, K_{4}, C_{6}$, and $K_{3,3}$, and $\Delta(G)+2$ otherwise. (2). In 2016, Kalinowski, Pilsniak, and Wozniak introduced the total distinguishing number $D''(G)$ of $G$. Inspired by a recent result of Mirafzal (2024), we show that the distinguishing number $D(S(G))$ of the subdivision graph $S(G)$ of $G$ is $D''(G)$. Consequently, $D(S(G))$ is at most $\lceil \sqrt{\Delta(G)}\rceil$. (3). We obtain a sharp upper bound for the distinguishing chromatic number of the subdivision graph $S(G)$ of $G$ in terms of the distinguishing number of $G$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims three results on distinguishing parameters. For the middle graph M(G) of any simple finite connected G with n≥3, χ_D(M(G)) equals Δ(G)+1 except for the four graphs C_4, K_4, C_6 and K_{3,3} (where it equals Δ(G)+2); this follows from applying the 1976 Hamada-Yoshimura theorem on middle graphs together with the distinguishing-chromatic-number theorems of Kalinowski-Pilsniak (2015) and Alikhani-Soltani (2020). It further shows that the distinguishing number D(S(G)) of the subdivision graph equals the total distinguishing number D''(G) introduced in 2016, yielding D(S(G)) ≤ ⌈√Δ(G)⌉, and supplies a sharp upper bound on χ_D(S(G)) in terms of D(G).

Significance. If the cited theorems apply directly to the middle-graph and subdivision constructions, the manuscript supplies explicit closed-form values for χ_D on two standard derived graphs and an identification between D and D'' on subdivisions. These would be concrete additions to the literature on distinguishing numbers, provided the transfer of hypotheses is justified.

major comments (2)
  1. [main theorem on middle graphs] The classification of χ_D(M(G)) for arbitrary connected G (abstract and the statement of the main theorem on middle graphs) rests entirely on the direct applicability of Hamada-Yoshimura (1976) and the 2015/2020 distinguishing-chromatic results to M(G). The manuscript provides no explicit verification that the automorphism group and proper-coloring constraints induced by the middle-graph construction (vertices of G plus one per edge) satisfy the hypotheses of those theorems for every G with n≥3; this is load-bearing for the claim that only four exceptions exist.
  2. [result on subdivision graphs] The equality D(S(G)) = D''(G) (the second main result) is derived from Mirafzal (2024). The manuscript must detail the precise correspondence between total distinguishing labelings of G and distinguishing labelings of S(G), including how the added subdivision vertices affect the automorphism group; without this, the transfer to the bound ⌈√Δ(G)⌉ remains unexamined.
minor comments (2)
  1. [abstract] The abstract refers to 'some recent results' of Alikhani-Soltani (2020) and Kalinowski-Pilsniak (2015) without naming the specific theorems invoked; the introduction should state the exact statements used.
  2. Notation for distinguishing chromatic number is introduced as χ_D but later appears as χ_{D}; standardize throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. The comments correctly identify places where the manuscript would benefit from expanded explanations of how the cited theorems apply to the derived graphs. We will revise the paper to include these details.

read point-by-point responses

  1. Referee: [main theorem on middle graphs] The classification of χ_D(M(G)) for arbitrary connected G (abstract and the statement of the main theorem on middle graphs) rests entirely on the direct applicability of Hamada-Yoshimura (1976) and the 2015/2020 distinguishing-chromatic results to M(G). The manuscript provides no explicit verification that the automorphism group and proper-coloring constraints induced by the middle-graph construction (vertices of G plus one per edge) satisfy the hypotheses of those theorems for every G with n≥3; this is load-bearing for the claim that only four exceptions exist.

    Authors: We agree that an explicit verification is needed to make the argument self-contained. In the revised version we will add a dedicated subsection that (i) recalls the precise statement of the Hamada–Yoshimura theorem on the chromatic number of middle graphs, (ii) describes the automorphism group of M(G) in terms of Aut(G) and the edge-vertex incidences, and (iii) checks that the proper-coloring and distinguishing constraints required by the Kalinowski–Pilsniak and Alikhani–Soltani theorems hold for every connected G with n≥3. The four exceptional graphs will be treated separately with direct computation. This addition will justify the claim that χ_D(M(G)) equals Δ(G)+1 except for those four graphs. revision: yes

  2. Referee: [result on subdivision graphs] The equality D(S(G)) = D''(G) (the second main result) is derived from Mirafzal (2024). The manuscript must detail the precise correspondence between total distinguishing labelings of G and distinguishing labelings of S(G), including how the added subdivision vertices affect the automorphism group; without this, the transfer to the bound ⌈√Δ(G)⌉ remains unexamined.

    Authors: We accept that the correspondence must be spelled out. The revised manuscript will contain an expanded proof that explicitly constructs a bijection between total distinguishing labelings of G and distinguishing labelings of S(G). We will also analyze the action of Aut(S(G)) on the original vertices and the new subdivision vertices, showing that any automorphism of S(G) that preserves the labeling must arise from a total distinguishing labeling of G (and conversely). This will rigorously justify the equality D(S(G)) = D''(G) and the consequent bound ⌈√Δ(G)⌉. revision: yes

Circularity Check

0 steps flagged

No circularity; results apply external theorems without self-referential reduction

full rationale

The paper states it applies results from Hamada-Yoshimura (1976), Alikhani-Soltani (2020) and Kalinowski-Pilsniak (2015) to obtain χ_D(M(G)) = Δ(G)+1 (with four listed exceptions) and proves D(S(G)) = D''(G) inspired by Mirafzal (2024). All cited works have no author overlap with the present paper. No equations, definitions or proofs in the abstract reduce a claimed output to a fitted input or prior self-citation by construction. The derivation therefore rests on independent external support rather than internal circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities; full manuscript required for audit.

pith-pipeline@v0.9.0 · 5809 in / 1120 out tokens · 50047 ms · 2026-05-23T17:39:45.666095+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    M. O. Albertson and K. L. Collins, Symmetry Breaking in Graphs, Electron. J. of Combin. 3 (1996), no. 1. doi:https://doi.org/10.37236/1242

    work page doi:10.37236/1242 1996

  2. [2]

    Alikhani and S

    S. Alikhani and S. Soltani, The chromatic distinguishing index of cer tain graphs, AKCE Int J Graphs Co. 17 (2020), no. 1, 131–138. doi: https://doi.org/10.1016/j.akcej.2019.03.008

    work page doi:10.1016/j.akcej.2019.03.008 2020

  3. [3]

    K. L. Collins, M. Hovey, and A. N. Trenk, Bounds on the Distinguish ing Chromatic Number, Electron. J. of Combin. 16 (2009) no. 1. doi: https://doi.org/10.37236/177

    work page doi:10.37236/177 2009

  4. [4]

    K. L. Collins and A. N. Trenk, The Distinguishing Chromatic Number, Electron. J. of Combin. 13 (2006). doi: https://doi.org/10.37236/1042

    work page doi:10.37236/1042 2006

  5. [5]

    Hamada and I.Yoshimura, Traversability and connectivity of th e middle graph of a graph, Discrete Math

    T. Hamada and I.Yoshimura, Traversability and connectivity of th e middle graph of a graph, Discrete Math. 14 (1976) no. 3, 247–255. doi: https://doi.org/10.1016/0012-365X(76)90037-6

    work page doi:10.1016/0012-365x(76)90037-6 1976

  6. [6]

    S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim. 9 (2024) no. 2, 297-307. doi: https://doi.org/10.22049/cco.2023.28270.1494

    work page doi:10.22049/cco.2023.28270.1494 2024

  7. [7]

    Nihei, On the chromatic number of middle graph of a graph, Pi Mu Epsilon Journal 10 (1998), no

    M. Nihei, On the chromatic number of middle graph of a graph, Pi Mu Epsilon Journal 10 (1998), no. 9, 704–708. url:http://www.jstor.org/stable/24340547

    work page arXiv 1998

  8. [8]

    Kalinowski, M

    R. Kalinowski, M. Pil´ sniak, M. Wo´ zniak: Distinguishing graphs by t otal colourings, Ars Math. Contemp. 11, 79-89 (2016), no. 1. doi: https://doi.org/10.26493/1855-3974.751.9a8

    work page doi:10.26493/1855-3974.751.9a8 2016

  9. [9]

    Kalinowski and M

    R. Kalinowski and M. Pil´ sniak, Distinguishing graphs by edge-colo urings, European J. Comb. 45 (2015), 124–131. doi: https://doi.org/10.1016/j.ejc.2014.11.003

    work page doi:10.1016/j.ejc.2014.11.003 2015

  10. [10]

    Sabidussi: Vertex-transitive graphs, Monatsh

    G. Sabidussi: Vertex-transitive graphs, Monatsh. Math. 68, 426-438 (1964). doi: https://doi.org/10.1007/BF01304186 Alfr´ ed R ´ enyi Institute of Mathematics, Re ´altanoda utca 13-15, 1053, Budapest, Hungary Email address, Corresponding author: banerjee.amitayu@gmail.com E¨otv¨os Lor ´and University, Department of Logic, M ´uzeum krt. 4, 1088, Budapest, H...

    work page doi:10.1007/bf01304186 1964