{"id":"ad9c959d-0025-4d21-8951-f32d47f8df79","arxiv_id":"2509.05143","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphs admiting color-avoiding connected colorings are exactly the sufficiently connected graphs, and for simple connectivity the minimum number of colors is computable in polynomial time.","lead":"This math paper studies networks where groups of links or nodes can fail together, modeled by colors. It identifies when such networks can stay connected after any one group fails, and how many colors are needed, plus which tasks are easy or impossible to compute efficiently.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4 NP-hardness reductions rely on an unproved gadget equivalence: replacing multi-color edge lists by paths of single-color edges plus s'' is asserted to preserve arc-1-color-avoiding strong/rooted connectivity, so Theorems 4.1–4.6 are unsupported if this fails.","rationale":"After checking the Section 3 core, I find the characterization results (Propositions 3.1–3.3) and the matroid-coloring result (Proposition 3.4, Corollary 3.5, Theorem 3.6) internally sound; the unique-color arguments and the dual-matroid proper-coloring equivalence are direct. The matroid algorithm relies only on a polynomial-time independence oracle for M*(G), which is available for graphs, so the polynomial-time claim is credible. The NP-hardness results in Section 3 (Corollaries 3.8, 3.10, 3.12) are also backed by cited reductions, and the counting argument for 4-regular Hamiltonian decomposition is valid. The only genuinely load-bearing gap I find is the single-color gadget equivalence in Section 4. The paper itself marks it with 'It is not difficult to show' twice, and no argument is supplied. Because the initial construction uses color lists rather than ordinary edge colorings, the reduction is incomplete unless the modification is proved. This does not make me suspect the results are false—the gadget has a plausible design—but the proof as written is conditional on an unverified equivalence. I therefore do not change the reader's conditional verdict.","tokens_in":29050,"tokens_out":32367,"duration_ms":359811,"concrete_test":"Prove or disprove the missing equivalence lemma for the Theorem 4.1 modification. Specifically, for every color c∈[m], show that after deleting c every s''-to-original-vertex path contains a c-colored segment, so s'' is attached to the core only through the surviving s''–s edges; and for c=m+1, all s''-to-vertex paths survive, so the color-m+1 condition is automatic. Use these facts to establish both directions: any arc-1-color-avoiding strongly connected orientation of the list-colored graph extends to the modified graph (orient each replacement-path pair bidirectionally), and conversely any such orientation of the modified graph restricts to one of the original after contracting intact replacement paths. If the converse fails on any small instance, run an exhaustive brute-force search over all color-list graphs on ≤5 vertices and ≤3 colors comparing existence before/after the modificat","verdict_should_be":"UNCHANGED","load_bearing_attack":"Location: Theorem 4.1, final paragraph of the proof; same assertion in Theorem 4.2. The reduction first builds an edge-colored graph whose edges are assigned lists of colors—a generalization not covered by the theorem statement—then claims: 'Let us replace each pair of parallel edges whose color list has length L≥2 with a path of L pairs of parallel edges... It is not difficult to show that this modified graph admits an arc-1-color-avoiding strongly 1-connected coloring if and only if φ can be satisfied.' No proof of either implication is given. The equivalence is load-bearing: the initial construction is only for multi-list edges, while the theorem's input is an ordinary single-color edge-colored graph; the NP-hardness for the single-color problem rests entirely on this modification. The replacement genuinely changes the graph: it subdivides edges into paths, introduces a new vertex s'', and changes deletion behavior (empty-list edges become color m+1). For colors j∈[m], the s''-to-vertex paths each contain a j-colored segment and are broken, so s'' can only connect through s; for color m+1, the original ∅-edges are deleted and s'' must substitute. It is not shown that no orientation of the modified graph uses these new paths to satisfy a formula that the original could not (or vice versa). The same gap appears in the rooted version (Theorem 4.2), and Theorems 4.3–4.6 reduce from Theorems 4.1–4.2, so the entire Section 4 complexity landscape depends on this omitted proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies color-avoiding connectivity in edge- and vertex-colored graphs and digraphs. Its main results are: existence characterizations for edge-ℓ-color-avoiding k-edge-connected colorings (iff the graph is (k+ℓ)-edge-connected, Prop. 3.1), analogous characterizations for vertex and internally vertex colorings, and the observation that for k=ℓ=1 the minimum number of colors equals the chromatic number of the dual matroid (Prop. 3.4, Cor. 3.5), giving a polynomial-time algorithm (Thm. 3.6). It also proves NP-hardness for k≥2 (Cor. 3.10) and for several orientation problems in Section 4, plus polynomial results for rooted colorings (Thms. 3.14–3.15). The paper is clearly written and honestly lists open problems, but the Section 4 hardness landscape is currently supported only by several asserted gadget equivalences that are not proved.","tokens_in":29461,"tokens_out":24683,"duration_ms":269016,"significance":"If the Section 4 reductions are completed, the paper would give a fairly comprehensive complexity map for color-avoiding connectivity under correlated edge/vertex failures. The matroid-duality characterization (Prop. 3.4, Cor. 3.5) is an elegant and apparently new bridge between color-avoiding connectivity and matroid coloring, and it yields a genuine polynomial-time algorithm. Several existence characterizations in Section 3 (Props. 3.1, 3.17, 3.20) are clean and use standard tools appropriately. The paper also identifies open cases honestly. However, the orientation NP-hardness claims in Section 4 are load-bearing and currently rest on unproved 'it is not difficult to show' equivalences, so the significance of that part of the paper is conditional until those proofs are supplied.","major_comments":[{"comment":"The reduction first constructs a graph whose edges are assigned lists of colors, which is not an instance of the stated single-color problem. The conversion replaces length-L lists by paths of L parallel-edge pairs, replaces empty lists by color m+1 edges, and adds a new vertex s''. The assertion that the modified graph admits an arc-1-color-avoiding strongly (or rooted) connected orientation iff φ is satisfiable is made without proof in either direction. This is load-bearing: the hardness of the single-color variant rests entirely on this equivalence, since the preceding argument applies only to the list instance. The modification genuinely changes deletion behavior: empty-list edges become deletable under color m+1, and s'' provides new connectivity. Both implications need a complete proof, including the behavior when color m+1 is removed. The same gap propagates to Theorems 4.3–4.6, w","section":"Theorem 4.1, final paragraph; Theorem 4.2, final paragraph"},{"comment":"These proofs also rely on 'it is not difficult to show' statements that are load-bearing. In Theorem 4.3, both the existence direction and the extraction of an orientation of G from an orientation of G' need proof that the three copies of each original vertex and the hubs v'', v''' do not create or destroy color-avoiding strong connectivity. In Theorem 4.5, Lemma 2.10(2) is invoked to pass from vertex- to internally vertex-color-avoiding, but the hypotheses of that lemma (every vertex has an in- and an out-neighbor of a different color) are not verified for G' under the relevant orientations. If any of these equivalences fail, the hardness results for vertex-colored orientations are unsupported. Please supply full arguments or modify the reductions so that the equivalences are directly proved.","section":"Theorems 4.3–4.6"},{"comment":"The sentence 'the arc set {v_i u_i | i∈B_j} forms a directed cut' is not justified as written. A directed cut is defined via a nonempty proper vertex set with no arcs in one direction; the proof does not identify that vertex set or check that no crossing arcs exist after color j is removed. The intended argument can likely be repaired by considering the component containing s', the v_i's, the u_i's, and w_j, but this needs to be written out explicitly. Since this is part of the NP-hardness proof, it should be made precise.","section":"Theorem 4.1, converse direction"}],"minor_comments":[{"comment":"The text says 'strongly 1-connected coloring' in a theorem about rooted connectivity; should be 'r-rooted 1-connected coloring'.","section":"Theorem 4.2, final paragraph"},{"comment":"In the sentence about choice number, 'from any lists of length at most k' should presumably be 'from any lists of length at least k'.","section":"Section 3.1.2"},{"comment":"The statement begins 'Let D be a graph' but should be 'Let D be a digraph'.","section":"Theorem 3.16"},{"comment":"The sufficiency direction ('assign a unique color to each vertex') is correct, but a one-sentence justification—that deleting at most ℓ vertices from a (k+ℓ)-vertex-connected graph leaves a k-vertex-connected graph—would improve readability.","section":"Proposition 3.20"},{"comment":"Typos include 'an an instance' in the proofs of Theorems 4.1 and 4.2, 'dge-colored' in Theorem 4.5, and 'edge-1-color-avoiding graph' in the Section 4 introduction.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. Section 3 is the real meat: the characterization results are clean, and Corollary 3.5 / Theorem 3.6 — min colors for edge-1-color-avoiding connected coloring equals χ(M*(G)), poly-time via matroid partitioning — is a genuinely nice connection that I hadn't seen stated before. The rooted digraph result (Theorem 3.14) is also solid and gives a rare exact answer. The NP-hardness results for k≥2 and the weighted variants are standard but correct reductions, and the paper does a good job unifying a fragmented literature and flagging what stays open.\n\nThe soft spot is Section 4, and the reader's strongest concern is on target. In the proofs of Theorems 4.1 and 4.2, after building an instance where edges carry lists of colors, the authors need to convert that to a genuine edge-coloring (one color per edge). The conversion — replacing each multi-color parallel pair by a path of single-color parallel pairs, adding s'' in 4.1, and recoloring the empty-list edges — is asserted with \"it is not difficult to show.\" But that equivalence is load-bearing. The modification changes deletion behavior and the set of possible orientations; without a proof in either direction, the hardness of the single-color problem does not follow. The later theorems in Section 4 reduce from 4.1/4.2, so the whole orientation-complexity landscape in that section is conditional. I would not desk-reject; I would send it to a referee and ask for the missing details, because the rest of the paper suggests the claim is likely true and fixable.\n\nOne place I disagree with the reader: Proposition 3.20's sufficiency is fine. Assigning a unique color to each vertex works: if G is (k+ℓ)-vertex-connected, deleting the vertices of any ℓ colors deletes at most ℓ vertices, leaving a k-vertex-connected graph. So that's not a gap.\n\nBottom line: Section 3 is a solid contribution; Section 4 needs work before the results are fully established. The paper deserves a serious referee, and I would cite the matroid-dual result even now.","headline":"Section 3 has a genuinely useful matroid-dual characterization and poly-time min-color result, but Section 4's NP-hardness proofs rest on an unproved gadget equivalence that needs to be nailed down before the complexity results are fully credible.","tokens_in":29911,"tokens_out":3345,"would_cite":true,"duration_ms":35510,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","05C20","05C15","05B35","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph admits a coloring that survives the deletion of any ℓ color classes exactly when it is (k+ℓ)-edge-connected, and for k=1 the fewest colors is a matroid invariant computable in polynomial time.","keywords":["color-avoiding connectivity","correlated failures","edge-colored graphs","dual matroid chromatic number","courteous coloring","matroid coloring","strong connectivity orientation","NP-completeness"],"falsifier":"Apply the replacement described after Theorem 4.1 to a small edge-colored graph: replace each multi-color parallel pair by a path of single-color parallel pairs and add vertex s′′ connected to every original vertex by m parallel-edge paths. Test whether the modified graph admits an arc-1-color-avoiding strongly connected orientation exactly when the original does; one mismatch would break the claimed reduction.","tokens_in":28973,"feed_emoji":"🎨","tokens_out":10895,"duration_ms":95156,"temperature":0.7,"pith_summary":"This paper asks what it takes for a network to keep working when whole groups of edges fail together. Grouping edges into color classes, it defines a graph as color-avoiding k-edge-connected if deleting all edges of any at most ℓ colors still leaves it k-edge-connected. The central result is a clean characterization: such a coloring exists exactly when the uncolored graph is (k+ℓ)-edge-connected—the failure groups can be hidden as long as the graph carries ℓ extra edge-disjoint paths. For the most basic case (k=1), the paper proves that the minimum number of colors equals the chromatic number of the dual graphic matroid and can be computed in polynomial time. It then maps every other variant: minimum-color problems for k≥2 and for strong orientations are NP-complete, while rooted directed colorings need exactly ℓ+1 colors and are polynomial-time solvable.","feed_headline":"A network survives any ℓ color failures iff it is (k+ℓ)-edge-connected","feed_subtitle":"For k=1, the fewest colors equals the dual matroid's chromatic number, computable in polynomial time.","key_machinery":"The load-bearing object is the ℓ-courteous coloring of a matroid: a coloring of the ground set such that deleting all elements of any at most ℓ colors never reduces the matroid rank. For graphic matroids this is exactly edge-ℓ-color-avoiding connectivity, and the key identity is that a coloring is 1-courteous if and only if it is a proper coloring of the dual matroid M*, transferring the minimum-color problem to matroid chromatic number and its polynomial-time partition algorithm. For rooted directed connectivity the carrying mechanism is the arborescence packing theorem—rooted k-arc-connectivity is the same as packing k arc-disjoint spanning arborescences—which makes ℓ+1 colors the exact in","core_discovery":"The paper's discovery is that correlated failures, though arbitrary in size, cannot consume more than their own number of colors from any cut. Precisely: G has an edge-ℓ-color-avoiding k-edge-connected coloring if and only if G is (k+ℓ)-edge-connected, because any cut of size ≤k+ℓ−1 contains at most ℓ colors plus at most k−1 leftover edges, and conversely coloring every edge with its own color removes at most ℓ edges per color attack. For k=1, the minimum-color question reduces to matroid theory: a coloring of the graphic matroid is 1-courteous—rank survives every single-color deletion—exactly when it is a proper coloring of the dual matroid M*(G); hence the minimum number of colors is χ(M*(","pith_inferences":["The (k+ℓ)-edge-connectivity characterization implies that correlated failure groups of any size are no harder to survive than a single edge—what matters is only the total number of groups that may fail, so planners can ignore group composition and test only surplus edge-connectivity.","The dual-matroid identity suggests a wider template: in any matroid, a minimum-color coloring that survives deletion of any ≤ℓ colors is governed by the dual's covering number, so analogous guarantees for branchings, matchings, or transversal systems could be certified with the same matroid partition machinery.","The unproved gadget equivalence in the orientation reductions is directly testable on small graphs; if a counterexample appears, Theorems 4.1–4.2 would need repair, whereas a proof would close the only gap in the hardness chain.","The two-color solvability for arc-color-avoiding strongly connected orientations and the openness at three colors suggest a natural threshold: the most likely boundary is that three colors make the orientation problem NP-complete."],"forward_implications":["Every (k+ℓ)-edge-connected graph is colorable—for instance by unique edge colors—so that deleting any ≤ℓ color classes still leaves it k-edge-connected, and no smaller edge-connectivity can suffice.","For 2-edge-connected graphs, the fewest colors in an edge-1-color-avoiding connected coloring is the chromatic number of the dual matroid M*(G), computable in polynomial time along with an optimal coloring.","For k≥2 the minimum-color edge-coloring problem is NP-complete even on 4-regular graphs with two colors, and the arc-color-avoiding strongly connected coloring problem is NP-complete even for k=ℓ=1.","For an r-rooted (ℓ+1)-arc-connected digraph, the minimum number of colors in an arc-ℓ-color-avoiding rooted connected coloring is exactly ℓ+1, and achieving it is polynomial-time.","Simultaneous orientation and coloring is easy exactly where the underlying uncolored orientation problem is easy: strongly k-arc-connected under vertex colors requires a 2k-edge-connected orientation, and rooted variants require a rooted k-arc-connected orientation; the internally-vertex and k≥3 strong-vertex cases inherit NP-hardness."],"supporting_citations":[{"why":"Supplies the starting NP-complete problem Positive-Linear-NAE-3SAT-Exact4, the base of the orientation hardness reductions in Theorems 4.1 and 4.2.","marker":"[11]"},{"why":"Provides the arborescence packing theorem: rooted k-arc-connectivity equals k arc-disjoint spanning arborescences, which forces the exact ℓ+1 color bound in Theorem 3.14.","marker":"[15]"},{"why":"Gives the polynomial matroid-partition algorithm used to find a minimum-color 1-courteous coloring in Theorem 3.6.","marker":"[16]"},{"why":"Establishes NP-completeness of decomposing a 4-regular graph into two Hamiltonian cycles, the base problem for Corollary 3.10 and Theorem 4.7.","marker":"[28]"},{"why":"Supplies the companion Hamiltonian-cycle decomposition hardness result cited with [28].","marker":"[32]"},{"why":"Provides NP-completeness of 2-coloring hypergraphs, the base problem for internally vertex-color-avoiding hardness in Theorems 3.21, 3.23, 4.13, and 4.14.","marker":"[31]"},{"why":"Contains the orientation theorem for strong k-arc-connectivity used for the two-color polynomial cases and for simultaneous orientation/coloring.","marker":"[38]"},{"why":"Reports the NP-completeness of two arc-disjoint strongly connected spanning subdigraphs, the base problem for Corollary 3.12.","marker":"[4]"},{"why":"Supplies the matroid fact that cuts are exactly the minimal rank-reducing sets, linking courteous colorings to the dual matroid in Proposition 2.5.","marker":"[41]"}],"fun_headline_variants":["Survive any ℓ color failures iff (k+ℓ)-edge-connected","Minimum colors for 1-color safety equals dual matroid chromatic number","Edge-color-avoiding connectivity: iff condition, PTIME for k=1","NP-hard to minimize color classes for k≥2, PTIME for k=1","One color failure at a time: dual matroid gives exact minimum"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"In the hardness proofs of Theorems 4.1 and 4.2, the step replacing multi-color edge lists by paths of single-color parallel edges (plus the auxiliary vertex s′′ in the strong case) is asserted—'It is not difficult to show'—to preserve the existence of the desired orientation, but the equivalence is not proved; if it fails, those NP-hardness results are not established for single-color edge lists.","fun_headline_variants_meta":{"raw":{"variants":["Survive any ℓ color failures iff (k+ℓ)-edge-connected","Minimum colors for 1-color safety equals dual matroid chromatic number","Edge-color-avoiding connectivity: iff condition, PTIME for k=1","NP-hard to minimize color classes for k≥2, PTIME for k=1","One color failure at a time: dual matroid gives exact minimum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000931,"raw_usage":{"total_tokens":3807,"prompt_tokens":710,"completion_tokens":3097,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":3010}},"tokens_in":454,"tokens_out":3097,"duration_ms":19191,"temperature":1.0,"reasoning_tokens":3010,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:34:57.158954+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the replacement described after Theorem 4.1 to a small edge-colored graph: replace each multi-color parallel pair by a path of single-color parallel pairs and add vertex s′′ connected to every original vertex by m parallel-edge paths. Test whether the modified graph admits an arc-1-color-avoiding strongly connected orientation exactly when the original does; one mismatch would break the claimed reduction.","supporting_citations":[{"cited_title":"Darmann and J","cited_arxiv_id":null,"evidence_quote":"Supplies the starting NP-complete problem Positive-Linear-NAE-3SAT-Exact4, the base of the orientation hardness reductions in Theorems 4.1 and 4.2."},{"cited_title":"Edmonds,Edge-disjoint branchings, Combinatorial Algorithms, 1973, pp","cited_arxiv_id":null,"evidence_quote":"Provides the arborescence packing theorem: rooted k-arc-connectivity equals k arc-disjoint spanning arborescences, which forces the exact ℓ+1 color bound in Theorem 3.14."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the polynomial matroid-partition algorithm used to find a minimum-color 1-courteous coloring in Theorem 3.6."},{"cited_title":"Kotzig,Z teorie konečných pravidelných grafov tretieho a štvrtého stupňa, Časopis Pro Pěstování Matematiky82(1): 76–92, 1957","cited_arxiv_id":null,"evidence_quote":"Establishes NP-completeness of decomposing a 4-regular graph into two Hamiltonian cycles, the base problem for Corollary 3.10 and Theorem 4.7."},{"cited_title":"Martin,Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes, Aequationes Mathematicae14(1–2): 37–40, 1976","cited_arxiv_id":null,"evidence_quote":"Supplies the companion Hamiltonian-cycle decomposition hardness result cited with [28]."},{"cited_title":"Lovász,Coverings and colorings of hypergraphs, Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing: 3–12, 1973","cited_arxiv_id":null,"evidence_quote":"Provides NP-completeness of 2-coloring hypergraphs, the base problem for internally vertex-color-avoiding hardness in Theorems 3.21, 3.23, 4.13, and 4.14."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the orientation theorem for strong k-arc-connectivity used for the two-color polynomial cases and for simultaneous orientation/coloring."},{"cited_title":"Bang-Jensen and G","cited_arxiv_id":null,"evidence_quote":"Reports the NP-completeness of two arc-disjoint strongly connected spanning subdigraphs, the base problem for Corollary 3.12."},{"cited_title":"Recski,Matroid Theory and its Applications in Electric Network Theory and in Statics, Algorithms and Combinatorics, Springer, 1989","cited_arxiv_id":null,"evidence_quote":"Supplies the matroid fact that cuts are exactly the minimal rank-reducing sets, linking courteous colorings to the dual matroid in Proposition 2.5."}],"review_version":1}