Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

On the distinguishing chromatic number in hereditary graph classes

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves χ_D(G) ≤ Δ+2 for connected claw-free graphs, with equality only for C6 and K_{n/2}[2K1], and gives matching bounds for other hereditary classes.

desk verdict New tight bounds for distinguishing chromatic number in several hereditary classes, but the claw-free section has a concrete exceptional-graph typo (L(K1,3) is K3, not the intended L(K3,3)) that must be fixed. read the letter →

arxiv 2505.17193 v1 pith:CRSGINJW submitted 2025-05-22 math.CO

Christoph Brause , Rafa{l} Kalinowski , Monika Pilśniak , Ingo Schiemeyer This is my paper · ORCID
classification math.CO MSC 05C1505E18
keywords distinguishingchromaticnumberhereditarygraphclassesclaw-freegraphsC4-free2K2-freechordalH-freeautomorphisms
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

The paper studies the distinguishing chromatic number χ_D(G), the fewest colors in a proper vertex coloring that only the identity automorphism preserves, and asks how much the universal upper bound 2Δ(G) can be improved when small induced subgraphs are forbidden. It proves tight upper bounds for connected C4-free, chordal, (C4,2K2)-free, 2K2-free, claw-free, and (claw, diamond)-free graphs, and it characterizes the graphs attaining equality in each case. The headline result is that every connected claw-free graph satisfies χ_D(G) ≤ Δ(G)+2, with equality exactly for the 6-cycle and the complete join of n/2 copies of 2K1, denoted K_{n/2}[2K1]; all other claw-free graphs actually fit in Δ(G)+1 colors. These results matter because they show that the worst case of the Collins–Trenk bound is extremely rare once even one small induced subgraph is forbidden, and they give exact descriptions of the exceptions.

What carries the argument

The argument runs through several reusable mechanisms. For C4-free graphs, a lemma builds a distinguishing coloring inductively by layering distance layers from a chosen vertex u, using the absence of C4 to control color reuse and to force automorphisms to fix each layer. For chordal graphs, the proof inducts on simplicial vertices, whose existence is guaranteed in chordal graphs, and reduces to the structure of symmetric trees. For 2K2-free graphs, a dominating clique supplies an anchor that lets the coloring fix one vertex and then all others. For claw-free graphs, the central object is the decomposition into minimal non-complete dominating modules: the paper asserts that χ_D(G) is the sum of χ_D on these modules and that each module can be colored with χ(G_i)+1 colors, with the claw-free condition ensuring the module-splitting lemma. Finally, Section 5 translates the problem for (claw, diamond)-free graphs to distinguishing edge-colorings of a root graph via the Whitney isomorphism theorem.

What would settle it

Search a connected claw-free graph G with p(G) ≥ 2 for which the asserted additivity χ_D(G) = Σ χ_D(G_i) fails; concrete candidates are built from two disconnected components each equal to K_n ∪ K_n joined in a claw-free way, since the proof's last case depends on each part being an independent set. If any such graph satisfies χ_D(G) < Σ χ_D(G_i), the extremal characterization of Theorem 14 no longer follows from the given proof.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the Collins–Trenk bound 2Δ(G) is rarely needed: in each hereditary class considered, the distinguishing chromatic number lies at most Δ(G)+2, usually Δ(G)+1, and the extremal graphs are explicitly listed. Theorem 14 is the sharpest statement: if G is connected and claw-free, then χ_D(G) ≤ Δ(G)+2, and equality holds if and only if G is the 6-cycle C6 or the graph K_{n/2}[2K1] obtained from a complete join of n/2 copies of 2K1. The paper also proves χ_D(G) ≤ Δ(G)+1 for connected C4-free graphs (except C6), for chordal graphs (with equality on symmetric trees and their leaf-clique augmentations, plus α(G)K1+K_{ω(G)-1}), for (C4,2K2)-free graphs (except C5 and α(G)K1+K_{ω(G)-1}), and for (claw, diamond)-free graphs (except C4 and C6); 2K2-free graphs satisfy χ_D(G) ≤ 2Δ(G)−ω(G)+2 with equality only on complete graphs and balanced complete bipartite graphs.

Load-bearing premise

The load-bearing premise is in the claw-free proof: after partitioning the graph into minimal non-complete dominating modules, the paper asserts without a fully written proof that the distinguishing chromatic number of the whole graph is exactly the sum of the distinguishing chromatic numbers of the parts; if some automorphism could mix the parts, the reduction to Theorem 14 collapses.

Editorial extensions

If this is right

  • Every connected claw-free graph other than C6 and K_{n/2}[2K1] has a proper distinguishing coloring using at most Δ(G)+1 colors, because Theorem 14's equality cases are exhaustive.
  • For connected C4-free graphs, the only graph that needs Δ+2 colors is the 6-cycle; all others fit in Δ+1 colors.
  • For chordal graphs, the bound Δ+1 is attained exactly by symmetric trees, their leaf-clique augmentations T_A and T_B, and the graphs α(G)K1+K_{ω(G)-1}; no other chordal graph can be an extremal example.
  • For 2K2-free graphs, the bound 2Δ−ω+2 interpolates between complete graphs and balanced complete bipartite graphs, both of which reach it.
  • For (claw, diamond)-free graphs, the problem reduces to edge-coloring: χ_D(G) ≤ Δ(G)+1 except for C4 and C6.

Reading between the lines

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

  • One could test whether the module additivity step in Section 4 can be replaced by a direct inductive argument on the module quotient; if it fails, the claw-free theorem still might hold but needs a different proof.
  • The extremal list K_{n/2}[2K1] suggests a wider family of complete joins of identical pieces may be the only obstruction to Δ+1 bounds in other hereditary classes.
  • The line-graph translation in Section 5 points to a natural extension: bounds on distinguishing chromatic number of claw-free graphs with forbidden diamonds may transfer to distinguishing chromatic index of graphs with bounded degree, with the four exceptional graphs in Theorem 15 as the only obstructions to Δ+1.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper studies the distinguishing chromatic number χ_D in hereditary graph classes defined by forbidding small induced subgraphs from {C4, 2K2, K1,3, K4, K4−e}. The main results are: for C4-free graphs, χ_D ≤ Δ+2 with equality only for C6 (Theorem 6); for chordal graphs, χ_D ≤ Δ+1 with a structural equality characterization (Theorem 7); for (C4,2K2)-free graphs, χ_D ≤ Δ+1 with equality for α(G)K1+Kω(G)−1 or C5 (Theorem 8); for 2K2-free graphs, χ_D ≤ 2Δ−ω+2 with equality for complete or balanced complete bipartite graphs (Theorem 10); for claw-free graphs, χ_D ≤ χ+p(G) except for C6 and one exceptional line graph (Theorem 13), yielding χ_D ≤ Δ+2 with equality iff G≅C6 or G≅Kn/2[2K1] (Theorem 14); and for (claw,diamond)-free graphs, χ_D ≤ Δ+1 except C4,C6, with consequences for Kk-free cases (Theorems 16–18). The proofs combine simplicial-vertex reductions, a structural lemma on non-complete dominating modules, and reductions to known results on distinguishing edge-colorings.

Significance. If the exceptional-graph issue described below is repaired, Theorem 14 is a substantial improvement over the Collins–Trenk universal bound 2Δ for all claw-free graphs, with a complete and appealing extremal characterization. The modular decomposition idea in Section 4 (minimal non-complete dominating modules, Lemma 11, and the additivity of χ_D over such modules) is elegant and likely to be useful beyond this paper. The paper also gives tight bounds for several other hereditary classes. The proofs are mostly detailed and rely on external benchmarks with published proofs, namely Cranston's theorem, the Collins–Trenk theorem, and the authors' earlier distinguishing-edge-coloring theorem. The stress-test concern about the additivity of χ_D over dominating modules does not land: because the modules are dominating, all cross-edges are present, and using disjoint color palettes forces every color-preserving automorphism to preserve each module individually, so the additivity claim is valid, although it is not explicitly justified in the text.

major comments (2)
  1. [Section 4, Observation 12 and Theorems 13–14] Observation 12 is false as stated: under standard notation L(K1,3) is the triangle K3, for which χ=3, Δ=2, and χ_D=3, not χ_D=5. The graph with the invariants χ=3, Δ=4, and χ_D=5 that is used in the proofs is L(K3,3). This is not a harmless typo: in the proof of Theorem 13, the second subcase of the bichromatic 6-cycle analysis uses the exceptional graph to conclude 'As G is distinct from L(K1,3), we get |S|≤2', and in the proof of Theorem 14 the case p(G)≤1 invokes 'the facts χ(H)=3 and Δ(H)=4' for H=L(K1,3); neither statement is true of K3. The surrounding arguments only make sense if the intended exception is L(K3,3). The authors should correct the exceptional graph throughout and re-verify the two arguments.
  2. [Section 4, proof of Theorem 13] The additivity assertions χ_D(G)=Σ_i χ_D(G_i) and χ(G)=Σ_i χ(G_i) are stated without proof. The chromatic additivity is immediate from the join structure of the dominating modules, and the distinguishing additivity follows because disjoint color palettes force each color-preserving automorphism to preserve each P_i setwise. This should be stated explicitly, since the entire modular reduction in Theorem 13 and the p(G)≥2 case of Theorem 14 depend on it.
minor comments (6)
  1. [Section 2, Lemma 4] In the displayed equation, 'χG(D)' should read 'χ_D(G)'.
  2. [Section 2, Lemma 4] 'Nota that χ_D(G)=|V(G)|' contains a typo; it should be 'Note that'.
  3. [Section 3, Theorem 7] The text refers to 'Fig.3' for the definition of a symmetric tree, but the example appears to be Figure 1; please correct the cross-reference.
  4. [Section 3, Theorem 7] In the proof, the notation 'BGS(ui)' is unclear; it should be typeset as B_{G-S}(u_i), and 'root of GS' should be 'root of G-S'.
  5. [Section 4, Theorem 14] 'Brook's theorem' should be 'Brooks' theorem'.
  6. [Section 5, Theorem 16] The reduction to line graphs relies on the assertion that every Beineke graph different from the claw contains an induced diamond. Please add a precise reference or a sentence verifying this fact from Beineke's list, since the assertion is the entire basis for the line-graph reduction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main bounds are derived from standard prior theorems and internal structural arguments; the self-cited edge-coloring theorem is independent published work, and the L(K1,3) issue is a correctness/notation problem, not a circular reduction.

full rationale

I walked the derivation chain for Theorems 6, 7, 8, 10, 13, 14, and 16-17. No step equates a conclusion to an input by definition, and no fitted parameter is relabeled as a prediction. The module decomposition in Theorem 13 uses the fact that each P_i is a dominating module, so all cross-edges between modules are present; the asserted additivity χ_D(G)=Σχ_D(G_i) follows from the resulting join structure and disjoint colour palettes, not from the theorem being proved. The only self-citations are Theorem 15 from [10] and the values from [11], both used in Section 5 to transfer distinguishing edge-colouring bounds to line graphs. These are prior published theorems with their own proofs and do not assume the present results, so under the stated rules they count as independent evidence and do not raise the circularity score. I also checked the proof of Theorem 14: its use of Theorem 13 and Brooks' theorem is a standard reduction, and the extremal graph K_{n/2}[2K1] is verified directly. Two non-circular issues are worth flagging for the record. First, Observation 12 states that L(K1,3) has χ(G)=3 and χ_D(G)=5, and the proof of Theorem 14 refers to the 'facts' χ(H)=3 and Δ(H)=4 for the exceptional graph; under standard notation L(K1,3) is the triangle K3, whose invariants are χ=3, Δ=2, χ_D=3, so the written proof contains an internal inconsistency in a proof-critical exception. This is a correctness/notation matter, not a circularity. Second, the module additivity in Theorem 13 is asserted without an explicit proof, but it is valid by the join/disjoint-palette argument and is not an instance of assuming the conclusion. Overall, the central claims have independent mathematical content and are not forced by self-citation or by definition.

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

The paper's results rest on a collection of established graph theory theorems (Collins-Trenk, Cranston, Rose, Beineke, Whitney, Brooks) and one self-cited edge-coloring bound. No ad hoc axioms or invented entities are introduced; the parameter p(G) and module partition are defined within the paper rather than assumed from outside.

assumptions (7)
  • domain assumption Collins-Trenk theorem: every connected graph satisfies χ_D(G) ≤ 2Δ(G)
    Invoked in the introduction and as the baseline bound throughout.
  • domain assumption Cranston's theorem: connected (C3,C4)-free graphs satisfy χ_D(G) ≤ Δ(G)+1 unless G ≅ C6
    Used in Theorem 6 to finish the C3-free case.
  • domain assumption Every chordal graph has at least one simplicial vertex (Rose's theorem)
    Used in Theorem 7 to set up induction on G−S.
  • domain assumption Beineke's line graph characterization: claw-free and diamond-free graphs are line graphs
    Used in Theorem 16 to transfer to edge-colorings.
  • standard math Whitney isomorphism theorem: Aut(H) ≅ Aut(L(H)) except for three small graphs
    Used in Theorem 16 to equate χ_D(L(H)) with χ'_D(H).
  • domain assumption Theorem 15 from [10]: every connected H of order ≥3 has χ'_D(H) ≤ Δ(H)+1 except C4, K4, C6, K3,3
    Used as a black box in Theorems 16 and 17; it is independent prior work by the same authors.
  • standard math Brooks' theorem: χ(G) ≤ Δ(G) for connected graphs except cliques and odd cycles
    Used in Theorem 14 to convert χ(G) bounds to Δ(G) bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the distinguishing chromatic number in hereditary graph classes." pith.science (2026). https://pith.science/paper/CRSGINJW

@misc{pith2026250517193,
  author       = {Pith},
  title        = {Pith review of: On the distinguishing chromatic number in hereditary graph classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CRSGINJW}},
  note         = {Machine review of arXiv:2505.17193}
}
abstract

The distinguishing chromatic number of a graph $G$, denoted $\chi_D(G)$, is the minimum number of colours in a proper vertex colouring of $G$ that is preserved by the identity automorphism only. Collins and Trenk proved that $\chi_D(G)\le 2\Delta(G)$ for any connected graph $G$, and the equality holds for complete balanced bipartite graphs $K_{p,p}$ and for $C_6$. In this paper, we show that the upper bound on $\chi_D(G)$ can be substantially reduced if we forbid some small graphs as induced subgraphs of $G$, that is, we study the distinguishing chromatic number in some hereditary graph classes.

Figures

Figures reproduced from arXiv: 2505.17193 by the authors.

Figure 1
Figure 1. An example of a symmetric tree Ts A tree Ts is symmetric if all non-leaves have maximum degree, one of these vertices is a root, and every leaf has the same distance to the root (see Fig.3). A graph G is symmetric if either it is a symmetric tree or it can be constructed from a symmetric tree Ts by A) either adding all edges between all leafs of NTs (v) for each support v ∈ V (Ts) (such a tree is denoted by TA), [P… view at source ↗
Figure 2
Figure 2. An example of a symmetric graph TA B) or adding all edges between all leafs of NTs (v) and adding a new vertex v ′ which is adjacent to all leafs of NTs (v) for each support v ∈ V (Ts) (such a tree is denoted by TB). Observe that a complete graph Kn is symmetric, since Kn = TA for the star Ts = K1,n−1 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. An example of a symmetric graph TB Theorem 7. If G is a connected chordal graph, then χD(G) ≤ ∆(G) + 1 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Graph G = 3K1 + K4 Collins and Trenk [5] proved that every tree T satisfies the inequality χD(T) ≤ ∆(T) + 1, and the equality holds only for symmetric trees. A distinguishing proper colouring c of a symmetric tree Ts of maximum degree ∆ may be chosen as follows. The ce…
Figure 5
Figure 5. Figure 5: The line graph L(K1,3) Observation 12. If G ∼= L(K1,3), then χ(G) = 3 and χD(G) = 5. Theorem 13. If G is a connected claw-free graph, then χD(G) ≤ χ(G) + p(G) 10 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On $k$-colorability of $(bull, H)$-free graphs

    math.CO 2025-09 conditional novelty 7.0 of 10

    For (bull,claw)-, (bull,chair,C5)-, and (bull,claw,C5)-free graphs, the paper lists all structures that force chromatic number above 4 or 5, and gives a k-colorability criterion for clique expansions of odd cycles.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [10]

    Kalinowski and M

    R. Kalinowski and M. Pil´ sniak, Distinguishing graphs by edge-colourings.European J. Com- bin., 45: (2015) 124–131. 5, 15

    work page 2015

  2. [1]

    Balachandran, S

    N. Balachandran, S. Padinhatteer, and P. Spiga, Vertex transitive graphsGwithχ D(G)> χ(G) and small automorphism group.Ars Math. Contemp., 17(1): (2019) 311–318. 1

    work page 2019

  3. [2]

    L. W. Beineke, Characterizations of Derived Graphs.J. Combin. Theory, 9:(1970) 129–135. 5

    work page 1970

  4. [3]

    Cavers and K

    M. Cavers and K. Seyffarth, Graphs with large distinguishing chromatic number.Electron. J. Combin., 20(1): (2013) #P19. 1, 3

    work page 2013

  5. [4]

    Chung, A

    F.R.K. Chung, A. Gy´ arf´ as, Zs. Tuza, and W.T. Trotter, The maximum number of edges in 2K2 graphs with bounded maximum degree,Discrete Math., 81 (1990) 129–135. 9

    work page 1990

  6. [5]

    Collins and A

    K. Collins and A. Trenk, The distinguishing chromatic number.Electron. J. Combin., 13(1): (2006) #R16. 1, 1, 3

    work page 2006

  7. [6]

    Cranston, Proper Distinguishing Colorings with Few Colors for Graphs with Girth at Least 5.Electron

    D. Cranston, Proper Distinguishing Colorings with Few Colors for Graphs with Girth at Least 5.Electron. J. Combin.25(3): (2018) #P3.5. 1, 2

    work page 2018

  8. [7]

    Diestel, Graph Theory, 5th Edition

    R. Diestel, Graph Theory, 5th Edition. Springer-Verlag, Berlin, Heidelberg, New York 2016. 1

    work page 2016

Show all 13 references
  1. [8]

    Fijavˇ z, S

    G. Fijavˇ z, S. Negami, and T. Sano, 3-connected planar graphs are 5-distinguishing colorable with two exceptions.Ars Math. Contemp., 4 (2011) 165–175. 1 15

    2011

  2. [9]

    H. A. Jung, Zu einem Isomorphiesatz von H. Whitney f¨ ur Graphen.Math. Ann., 164 (3): (1966) 270–271. 5

    1966

  3. [11]

    Kalinowski, M

    R. Kalinowski, M. Pil´ sniak, J. Przyby lo, and M. Wo´ zniak, How to personalize the vertices of a graph?European J. Combin., 40 (2014) 116–123. 5

    2014

  4. [12]

    Laflamme and K

    C. Laflamme and K. Seyffarth, Distinguishing chromatic numbers of bipartite graphs.Elec- tron. J. Combin., 16(1): (2009) #R76. 1

    2009

  5. [13]

    Rose, Triangulated graphs and the elimination process.J

    D.J. Rose, Triangulated graphs and the elimination process.J. Math. Anal. Appl., 32 (3): (1970) 597–609. 3 16

    1970

Pith tools

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