{"id":"3f9e41a3-3e55-4ebd-bfd8-314bf62c3b09","arxiv_id":"2505.17193","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"New tight upper bounds and equality characterizations for the distinguishing chromatic number of C4-free, chordal, 2K2-free, claw-free, and (claw,diamond)-free graphs.","lead":"This paper proves tighter bounds on the distinguishing chromatic number, the fewest colors in a proper vertex coloring that breaks all graph symmetries, for graph families defined by forbidden induced subgraphs. For example, it shows connected claw-free and C4-free graphs need at most Δ+2 colors, far below the general 2Δ bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exceptional graph in Theorems 13–14 is rendered as L(K1,3), which is K3 and contradicts the stated invariants; the proof only makes sense with L(K3,3), so the central case analysis is internally inconsistent as written.","rationale":"The central claim is Theorem 14, whose proof depends on Theorem 13. Reading the proof in good faith, the module additivity asserted in Theorem 13 is actually sound: each module P_i is dominating, so every outside vertex is complete to P_i, making G the join of the G_i; using disjoint palettes then prevents automorphisms from mixing modules and gives χ_D(G)=Σχ_D(G_i). The genuine load-bearing defect is the repeated misidentification of the exceptional graph. As rendered, L(K1,3) is K3, which has χ_D=3, not 5, and Δ=2, not 4. The proof's own 6-cycle construction, however, produces a 4-regular 9-vertex graph whose invariants match L(K3,3), so the notation is very likely a typo. Still, because the theorem statements and the p(G)≤1 case of Theorem 14 use this exception, the manuscript as written is internally inconsistent until the correction is made and verified. This warrants the same CONDITIONAL verdict: the bound may be correct, but the exceptional-case analysis must be fixed and the additivity step should be explicitly justified.","tokens_in":13818,"tokens_out":39091,"duration_ms":327153,"concrete_test":"Replace every occurrence of L(K1,3) with L(K3,3) and recompute Observation 12 for the rook graph R(3,3): Δ=4, χ=3, χ_D=5 via Whitney isomorphism and χ'_D(K3,3)=5. Then re-run the 6-cycle subcase: the graph obtained when |S_u|=|S_{u+}|=|S_{u2+}|=1 should be isomorphic to L(K3,3); if it is not, the exclusion is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Under standard notation L(K1,3) is the triangle K3, with χ(K3)=3, Δ(K3)=2, and χ_D(K3)=3. This contradicts Observation 12 (χ=3, χ_D=5) and the proof of Theorem 14, which uses χ(H)=3 and Δ(H)=4. The surrounding 6-cycle subcase shows the intended exception is L(K3,3), whose invariants are indeed χ=3, Δ=4, χ_D=5. Since Theorem 13's exclusion and Theorem 14's p(G)≤1 case both invoke this exception, the written proof has a concrete inconsistency in a proof-critical spot. The module additivity flagged as weakest by the reader is not the real issue: because every P_i is a dominating module, all cross-edges between P_i and P_j are present, and disjoint color palettes force every color-preserving automorphism to preserve each P_i, so χ_D(G)=Σχ_D(G_i) is valid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14036,"tokens_out":25134,"duration_ms":219417,"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":[{"comment":"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.","section":"Section 4, Observation 12 and Theorems 13–14"},{"comment":"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.","section":"Section 4, proof of Theorem 13"}],"minor_comments":[{"comment":"In the displayed equation, 'χG(D)' should read 'χ_D(G)'.","section":"Section 2, Lemma 4"},{"comment":"'Nota that χ_D(G)=|V(G)|' contains a typo; it should be 'Note that'.","section":"Section 2, Lemma 4"},{"comment":"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.","section":"Section 3, Theorem 7"},{"comment":"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'.","section":"Section 3, Theorem 7"},{"comment":"'Brook's theorem' should be 'Brooks' theorem'.","section":"Section 4, Theorem 14"},{"comment":"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.","section":"Section 5, Theorem 16"}],"recommendation":"major_revision","confidential_remarks":"The L(K1,3) error appears to be a local but proof-critical typo for L(K3,3); if the authors confirm this correction, the central results are likely salvageable. The paper's contribution is within scope and the novelty is adequate. No issues with citation norms beyond the requested verification in Theorem 16."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading for the C4-free and chordal results alone. Theorems 6 and 7 give tight Δ+2 and Δ+1 bounds with equality characterizations, and the proofs, while dense, look structurally sound. The 2K2-free bound and the (claw,diamond)-free section are also new and plausible. The claw-free results (Theorems 13 and 14) are the most ambitious, and they contain a concrete error.\n\nObservation 12 states that L(K1,3) has chromatic number 3 and distinguishing chromatic number 5. Under standard notation, L(K1,3) is the triangle K3, whose distinguishing chromatic number is 3. The intended exceptional graph is almost certainly L(K3,3), whose invariants do match χ=3, Δ=4, χ_D=5. The proof of Theorem 14 explicitly uses those invariants for L(K1,3), and Theorem 13 excludes it. So as written, the central case analysis in the claw-free section is internally inconsistent. This looks like a typo rather than a deep flaw, but it needs to be fixed and the surrounding cases rerun.\n\nI checked the module additivity that the reader flagged as a weakness. I don't think it's a problem. Since each P_i is a dominating module, every vertex outside P_i is complete to it, so the join structure is present. With disjoint color palettes, any color-preserving automorphism must preserve each P_i, so χ_D(G)=Σχ_D(G_i) and χ(G)=Σχ(G_i) hold. The real issue is the L(K1,3) mix-up.\n\nOther soft spots are minor. The chordal characterization proof has a few 'it is easy to see' steps, especially around the symmetric graphs, but nothing that looks wrong. The use of the authors' own prior result [10] for edge-distinguishing colorings is legitimate; it is a separately published theorem, not a circular dependency.\n\nIf the authors correct the exceptional graph, the paper deserves a serious referee. The bounds are new, the equality cases are non-trivial, and the writing is mostly careful. I would send it to peer review with the request that the claw-free section be re-examined after the correction.","headline":"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.","tokens_in":14582,"tokens_out":3834,"would_cite":false,"duration_ms":30282,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05E18"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["distinguishing chromatic number","hereditary graph classes","claw-free graphs","C4-free graphs","2K2-free graphs","chordal graphs","H-free graphs","graph automorphisms"],"falsifier":"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.","tokens_in":13639,"feed_emoji":"🎨","tokens_out":5843,"duration_ms":43347,"temperature":0.7,"pith_summary":"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.","feed_headline":"Claw-free graphs need at most Δ+2 distinguishing colors","feed_subtitle":"Tight bounds for many forbidden-subgraph classes, with equality cases C6 and K_{n/2}[2K1].","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the distinguishing chromatic number and proves the universal 2Δ bound that all improvements in the paper are measured against.","marker":"[5]"},{"why":"Proves χ_D ≤ Δ+1 for graphs of girth at least five, which motivates the forbidden-induced-subgraph viewpoint and supplies the (C3,C4)-free base case.","marker":"[6]"},{"why":"Characterizes graphs with χ_D ≥ |V(G)|−2, used in the 2K2-free proof to reduce to the case χ_D ≤ 2Δ−1.","marker":"[3]"},{"why":"Supplies the dominating clique of size ω(G) in connected 2K2-free graphs, the structural anchor for Theorem 10.","marker":"[4]"},{"why":"Establishes the distinguishing chromatic index bound Δ+1 with four exceptions, which Section 5 transfers to (claw, diamond)-free graphs via line graphs.","marker":"[10]"},{"why":"Gives the Whitney isomorphism theorem variant used to identify automorphisms of a line graph with automorphisms of its root graph.","marker":"[9]"},{"why":"Provides the classical fact that chordal graphs contain simplicial vertices, the induction step in the chordal theorem.","marker":"[13]"}],"fun_headline_variants":["Claw-free graphs use ≤ Δ+2 distinguishing colors","Claw-free graphs: χ_D ≤ Δ+2","Claw-free graphs need only Δ+2 colors to distinguish","Forbidding claws lowers distinguishing chromatic bound to Δ+2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Claw-free graphs use ≤ Δ+2 distinguishing colors","Claw-free graphs: χ_D ≤ Δ+2","Claw-free graphs need only Δ+2 colors to distinguish","Forbidding claws lowers distinguishing chromatic bound to Δ+2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001839,"raw_usage":{"total_tokens":7214,"prompt_tokens":917,"completion_tokens":6297,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":6228}},"tokens_in":533,"tokens_out":6297,"duration_ms":43488,"temperature":1.0,"reasoning_tokens":6228,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:53:19.711674+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Collins and A","cited_arxiv_id":null,"evidence_quote":"Introduces the distinguishing chromatic number and proves the universal 2Δ bound that all improvements in the paper are measured against."},{"cited_title":"Cranston, Proper Distinguishing Colorings with Few Colors for Graphs with Girth at Least 5.Electron","cited_arxiv_id":null,"evidence_quote":"Proves χ_D ≤ Δ+1 for graphs of girth at least five, which motivates the forbidden-induced-subgraph viewpoint and supplies the (C3,C4)-free base case."},{"cited_title":"Cavers and K","cited_arxiv_id":null,"evidence_quote":"Characterizes graphs with χ_D ≥ |V(G)|−2, used in the 2K2-free proof to reduce to the case χ_D ≤ 2Δ−1."},{"cited_title":"Chung, A","cited_arxiv_id":null,"evidence_quote":"Supplies the dominating clique of size ω(G) in connected 2K2-free graphs, the structural anchor for Theorem 10."},{"cited_title":"Kalinowski and M","cited_arxiv_id":null,"evidence_quote":"Establishes the distinguishing chromatic index bound Δ+1 with four exceptions, which Section 5 transfers to (claw, diamond)-free graphs via line graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Whitney isomorphism theorem variant used to identify automorphisms of a line graph with automorphisms of its root graph."},{"cited_title":"Rose, Triangulated graphs and the elimination process.J","cited_arxiv_id":null,"evidence_quote":"Provides the classical fact that chordal graphs contain simplicial vertices, the induction step in the chordal theorem."}],"review_version":1}