Pith. sign in

REVIEW 3 major objections 5 minor 52 references

Color-avoiding connected colorings and orientations

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.05143 v1 pith:IDDLKA44 submitted 2025-09-05 math.CO

József Pintér , Kitti Varga This is my paper · ORCID
classification math.CO MSC 05C4005C2005C1505B3568Q17
keywords color-avoidingconnectivitycorrelatedfailuresedge-coloredgraphsdualmatroidchromaticnumbercourteouscoloringstrongorientationNP-completeness
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 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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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*(

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

3 major / 5 minor

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.

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 (3)
  1. [Theorem 4.1, final paragraph; Theorem 4.2, final paragraph] 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
  2. [Theorems 4.3–4.6] 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.
  3. [Theorem 4.1, converse direction] 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.
minor comments (5)
  1. [Theorem 4.2, final paragraph] The text says 'strongly 1-connected coloring' in a theorem about rooted connectivity; should be 'r-rooted 1-connected coloring'.
  2. [Section 3.1.2] 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'.
  3. [Theorem 3.16] The statement begins 'Let D be a graph' but should be 'Let D be a digraph'.
  4. [Proposition 3.20] 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.
  5. [Throughout] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: derivation chain rests on external theorems and reductions; Section 4 contains an asserted gadget equivalence that is a proof gap, not a circular step.

full rationale

After walking the claimed derivation chain, I find no self-definitional, fitted-input, or load-bearing self-citation step. The main characterization (Proposition 3.1) is proved directly from the connectivity definitions via cut arguments; the minimum-color results (Proposition 3.4, Corollary 3.5, Theorem 3.6) follow from matroid duality and an independent oracle algorithm; the NP-hardness results in Section 3 reduce from external NP-complete problems (Bang-Jensen et al., Kotzig–Martin, Yeo) with explicit equivalences that are not tautological. The Section 4 reductions do contain an asserted but unproved gadget equivalence at the end of Theorem 4.1 (and similarly in Theorem 4.2): '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...' This is a genuine omitted proof and a correctness risk for the single-color hardness claims, but it is an omitted argument rather than a circular reduction—no equation or definition forces the conclusion. The only self-citation, [39], is background and supplies Lemma 2.10(1); the directed extensions of Lemma 2.10 are asserted rather than proved, but they are independent structural facts whose assumptions do not include the target results. Thus there is no substantial circularity; the paper's central derivations are self-contained against external benchmarks.

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

All results are derived from standard graph and matroid theory; no fitted parameters or new postulated entities. The main domain-specific assumptions are the nonstandard connectivity definitions and the oracle model for matroid algorithms.

assumptions (5)
  • standard math Menger's theorem connecting k-connectivity to absence of cuts of size less than k
    Used in Propositions 2.2 and 2.3 to give cut-based characterizations of color-avoiding connectivity.
  • standard math Edmonds' arborescence packing theorem
    Used in Theorem 3.14 to construct an (l+1)-color coloring from l+1 arc-disjoint spanning r-arborescences.
  • standard math Nash-Williams orientation theorem for strong k-arc-connectivity
    Used in Section 4 for deciding strongly k-arc-connected orientations and in Theorem 4.9.
  • domain assumption Nonstandard k-vertex-connectivity definitions for small graphs
    The paper treats one-vertex graphs with loops and two-vertex multigraphs as k-vertex-connected; Proposition 3.20 and related results rely on these definitions, which differ from common usage.
  • domain assumption Matroid oracle model for independence testing
    Theorem 3.6 assumes independence oracle access to the matroid. For graphic matroids this is polynomial-time implementable, but the abstract matroid result depends on the oracle model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Color-avoiding connected colorings and orientations." pith.science (2026). https://pith.science/paper/IDDLKA44

@misc{pith2026250905143,
  author       = {Pith},
  title        = {Pith review of: Color-avoiding connected colorings and orientations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IDDLKA44}},
  note         = {Machine review of arXiv:2509.05143}
}
abstract

We study network robustness under correlated failures modeled by colors, where each color represents a class of edges or vertices that may fail simultaneously. An edge-colored graph is said to be edge-color-avoiding $k$-edge-connected if it remains $k$-edge-connected after the removal of all edges of any single color. We characterize the graphs that admit such a coloring and show that, when $k = 1$, one can determine in polynomial time both the minimum number of colors required and a coloring achieving it; while the problem becomes NP-hard for $k \ge 2$. We also investigate the problem of orienting the edges of a graph so that the resulting digraph remains strongly or rooted connected even after the removal of all arcs of any single color. In addition, we explore generalizations involving vertex-colorings, $k$-vertex-connectivity, simultaneous failures of multiple colors and matroids.

Figures

Figures reproduced from arXiv: 2509.05143 by the authors.

Figure 1
Figure 1. An example for a graphic matroid: the ground set of the matroid is [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Examples for edge-ℓ-color-avoiding k-edge-connectivity. The first graph is not edge-1-color-avoiding 1-connected: after the removal of the red (denoted by rectangles) edges, the top vertex becomes isolated. The second graph is edge-1-color-avoiding 1-connected but not edge-1-color-avoiding 2-edge-connected: after the removal of edges of any single color, the graph remains connected, but not 2-edge-connected. The thi… view at source ↗
Figure 3
Figure 3. Examples for vertex- and internally vertex- [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Examples for arc-ℓ-color-avoiding r-rooted k-arc-connectivity. The first digraph is arc-1-color-avoiding r-rooted 1- connected but not arc-1-color-avoiding r-rooted 2-arc-connected: after the removal of arcs of any single color, the digraph remains r-rooted connected, …
Figure 5
Figure 5. Figure 5: v1 v2 v3 v4 v6 v5 e1 e2 e3 v1 v2 v3 v4 v5 v6 we1 we2 we3 [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: The first graph is an edge-1-color-avoiding 2-edge-connected graph that does not have an arc-1-color-avoiding strongly [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: An example for the constructions used in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. Figure 8: Given the edge-colored graph in Figure [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: An example for the constructions used in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p023_9.png]
Figure 10
Figure 10. Figure 10: An example for the construction used in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p025_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

  1. [1]

    Aharoni and E

    R. Aharoni and E. Berger,The intersection of a matroid and a simplicial complex, Transactions of the American Mathe- matical Society358(11): 4895–4917, 2006

    work page 2006

  2. [2]

    Aharoni, E

    R. Aharoni, E. Berger, and R. Ziv,The edge covering number of the intersection of two matroids, Discrete Mathematics 312(1): 81–85, 2012

    work page 2012

  3. [3]

    Bang-Jensen, D

    J. Bang-Jensen, D. Gonçalves, and I. L. Gørtz,Finding Well-Balanced Pairs of Edge-Disjoint Trees in Edge-Weighted Graphs, Discrete Optimization4(3–4): 334–348, 2007

    work page 2007

  4. [4]

    Bang-Jensen and G

    J. Bang-Jensen and G. Z. Gregory,Digraphs: Theory, Algorithms and Applications, Second Edition, Springer Monographs in Mathematics, Springer, 2008

    work page 2008

  5. [5]

    Bérczi and T

    K. Bérczi and T. Schwarcz,Complexity of packing common bases in matroids, Mathematical Programming188(3–4): 1–18, 2021

    work page 2021

  6. [6]

    Bhalgat, R

    A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi,Fast edge splitting and Edmonds’ arborescence construction for unweighted graphs, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 455– 464

    work page 2008

  7. [7]

    Cheriyan and J

    J. Cheriyan and J. H. Reif,Directeds-tnumberings, rubber bands, and testing digraphk-vertex connectivity, Combinatorica 14(4): 435–451, 1994

    work page 1994

  8. [8]

    Coudert, P

    D. Coudert, P. Datta, S. Pérennes, H. Rivano, and M.-E. Voge,Shared risk resource group: Complexity and approximability Issues, Parallel Processing Letters17(2): 169–184, 2007

    work page 2007

Show all 52 references
  1. [9]

    Coudert, S

    D. Coudert, S. Pérennes, H. Rivano, and M.-E. Voge,Combinatorial optimization in networks with shared risk link groups, Discrete Mathematics & Theoretical Computer Science18(3) (Distributed Computing and Networking), article no. 8, 2016

    2016

  2. [10]

    C. R. Coullard and L. Hellerstein,Independence and port oracles for matroids, with an application to computational learning theory, Combinatorica16(2): 189–208, 1996

    1996

  3. [11]

    Darmann and J

    A. Darmann and J. Döcker,On a simple hard variant ofNot-All-Equal 3-Sat, Theoretical Computer Science815: 147–152, 2020

    2020

  4. [12]

    edu/~pds/papers/cutcolouring/paper.pdf

    M.DeVos,T.Johnson,andP.Seymour,Cut coloring and circuit covering,2006.Availableathttps://web.math.princeton. edu/~pds/papers/cutcolouring/paper.pdf

    2006

  5. [13]

    Durand de Gevigney,Graphs orientations: structures and algorithms, PhD Thesis, Université de Grenoble, 2014, https://theses.hal.science/tel-00989808/document

    O. Durand de Gevigney,Graphs orientations: structures and algorithms, PhD Thesis, Université de Grenoble, 2014, https://theses.hal.science/tel-00989808/document

    2014

  6. [14]

    Durand de Gevigney,On Frank’s conjecture onk-connected orientations, Journal of Combinatorial Theory, Series B 141: 105–114, 2020

    O. Durand de Gevigney,On Frank’s conjecture onk-connected orientations, Journal of Combinatorial Theory, Series B 141: 105–114, 2020

    2020

  7. [15]

    Edmonds,Edge-disjoint branchings, Combinatorial Algorithms, 1973, pp

    J. Edmonds,Edge-disjoint branchings, Combinatorial Algorithms, 1973, pp. 91–96

    1973

  8. [16]

    J. Edmonds,Minimum partition of a matroid into independent subsets, Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics69B(1–2): 67–72, 1965

    1965

  9. [17]

    F. V. Fomin, P. A. Golovach, T. Korhonen, D. Lokshtanov, and S. Saurabh,Fixed-parameter tractability of hedge cut, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025, pp. 1402–1411

    2025

  10. [18]

    Frank,An algorithm for submodular functions on graphs, North-Holland Mathematics Studies66: 97–120, 1982

    A. Frank,An algorithm for submodular functions on graphs, North-Holland Mathematics Studies66: 97–120, 1982

    1982

  11. [19]

    Frank,On the orientation of graphs, Journal of Combinatorial Theory, Series B28(3): 251–261, 1980

    A. Frank,On the orientation of graphs, Journal of Combinatorial Theory, Series B28(3): 251–261, 1980

    1980

  12. [20]

    H. N. Gabow,A framework for cost-scaling algorithms for submodular flow problems, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993, pp. 449—458

    1993

  13. [21]

    H. N. Gabow and K. S. Manu,Packing algorithms for arborescences (and spanning trees) in capacitated graphs, Mathe- matical Programming82: 83–109, 1998

    1998

  14. [22]

    Ghaffari, D

    M. Ghaffari, D. R. Karger, and D. Panigrahi,Random contractions and sampling for hypergraph and hedge connectivity, Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, pp. 1101–1114

    2017

  15. [23]

    Hausmann and B

    D. Hausmann and B. Korte,Algorithmic versus axiomatic definitions of matroids, Mathematical Programming at Ober- wolfach, 1981, pp. 98–111

    1981

  16. [24]

    Huck,Disproof of a conjecture about independent branchings ink-connected directed graphs, Journal of Graph Theory 20(2): 235–239, 1995

    A. Huck,Disproof of a conjecture about independent branchings ink-connected directed graphs, Journal of Graph Theory 20(2): 235–239, 1995

    1995

  17. [25]

    Iwata and Y

    S. Iwata and Y. Kobayashi,An algorithm for minimum cost arc-connectivity orientations, Algorithmica56: 437—447, 2010

    2010

  18. [26]

    Jaffke, P

    L. Jaffke, P. T. Lima, T. Masařík, M. Pilipczuk, and U. S. Souza,A tight quasi-polynomial bound for global label min-cut, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023, pp. 290–303

    2023

  19. [27]

    Kadović, S

    A. Kadović, S. M. Krause, G. Caldarelli, and V. Zlatić,Bond and site color-avoiding percolation in scale-free networks, Physical Review E98(6), article no. 062308, 2018. 29

    2018

  20. [28]

    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

    A. 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

    1957

  21. [29]

    S. M. Krause, M. M. Danziger, and V. Zlatić,Hidden connectivity in networks with vulnerable classes of nodes, Physical Review X6(4), article no. 041022, 2016

    2016

  22. [30]

    S. M. Krause, M. M. Danziger, and V. Zlatić,Color-avoiding percolation, Physical Review E96(2), article no. 022313, 2017

    2017

  23. [31]

    Lovász,Coverings and colorings of hypergraphs, Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing: 3–12, 1973

    L. Lovász,Coverings and colorings of hypergraphs, Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing: 3–12, 1973

    1973

  24. [32]

    Martin,Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes, Aequationes Mathematicae14(1–2): 37–40, 1976

    P. Martin,Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes, Aequationes Mathematicae14(1–2): 37–40, 1976

    1976

  25. [33]

    Menger,Zur allgemeinen Kurventheorie, Fundamenta Mathematicae10(1): 96–115, 1927

    K. Menger,Zur allgemeinen Kurventheorie, Fundamenta Mathematicae10(1): 96–115, 1927

    1927

  26. [34]

    Molontay and K

    R. Molontay and K. Varga,On the complexity of color-avoiding site and bond percolation, SOFSEM 2019: Theory and Practice of Computer Science, 2019, pp. 354–367

    2019

  27. [35]

    Morawietz, N

    N. Morawietz, N. Grüttemeier, C. Komusiewicz, and F. Sommer,Refined parameterizations for computing colored cuts in edge-colored Graphs, Theory of Computing Systems: 1019–1045, 2022

    2022

  28. [36]

    hu/memmorg/index.php/open-problems/partitioning-the-ground-set-of-a-matroid/

    MTA-ELTE Matroid Optimization Research Group,Partitioning the ground set of a matroid,https://berkri.web.elte. hu/memmorg/index.php/open-problems/partitioning-the-ground-set-of-a-matroid/. Accessed 5 September, 2025

    2025

  29. [37]

    C. St. J. A. Nash-Williams,Edge-Disjoint Spanning Trees of Finite Graphs, Journal of the London Mathematical Society 36(1): 445–450, 1961

    1961

  30. [38]

    C. St. J. A. Nash-Williams,On orientations, connectivity and odd-vertex-pairings in finite graphs, Canadian Journal of Mathematics12: 555–567, 1960

    1960

  31. [39]

    Pintér and K

    J. Pintér and K. Varga,Color-avoiding connected spanning subgraphs with minimum number of edges, Discrete Applied Mathematics349: 25–43, 2024

    2024

  32. [40]

    Plehn,Über die Existenz und das Finden von Subgraphen, PhD Thesis, University of Bonn, 1991,https://theses.hal

    J. Plehn,Über die Existenz und das Finden von Subgraphen, PhD Thesis, University of Bonn, 1991,https://theses.hal. science/tel-00989808/document

    1991

  33. [41]

    Recski,Matroid Theory and its Applications in Electric Network Theory and in Statics, Algorithms and Combinatorics, Springer, 1989

    A. Recski,Matroid Theory and its Applications in Electric Network Theory and in Statics, Algorithms and Combinatorics, Springer, 1989

    1989

  34. [42]

    H. E. Robbins,A theorem on graphs with an application to a problem of traffic control, American Mathematical Monthly 46(5): 281–283, 1939

    1939

  35. [43]

    G. C. Robinson and D. A. Welsh,The computational complexity of matroid properties, Mathematical Proceedings of the Cambridge Philosophical Society87(1): 29–45, 1980

    1980

  36. [44]

    Stapelen en overdekken

    A. Schrijver,Fractional packing and covering, Packing and Covering in Combinatorics (Study week "Stapelen en overdekken", Amsterdam, The Netherlands, June 5-9, 1978), 1979, pp. 201–274

    1978

  37. [45]

    P. D. Seymour,A note on list arboricity, Journal of Combinatorial Theory, Series B72(1): 150–151, 1998

    1998

  38. [46]

    Sheyner, J

    O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. M. Wing,Automated generation and analysis of attack graphs, Proceedings of the IEEE Symposium on Security and Privacy (S&P): 273–284, 2002

    2002

  39. [47]

    R. E. Tarjan,A good algorithm for edge-disjoint branching, Information Processing Letters3(2): 51—53, 1974

    1974

  40. [48]

    Thomassen,Strongly 2-connected orientations of graphs, Journal of Combinatorial Theory, Series B110: 67–78, 2015

    C. Thomassen,Strongly 2-connected orientations of graphs, Journal of Combinatorial Theory, Series B110: 67–78, 2015

    2015

  41. [49]

    W. T. Tutte,On the problem of decomposing a graph intonconnected factors, Journal of the London Mathematical Society 36(1): 221–230, 1961

    1961

  42. [50]

    R. W. Whitty,Vertex-disjoint paths and edge-disjoint branchings in directed graphs, Journal of Graph Theory11(3): 349–358, 1987

    1987

  43. [51]

    Xu and A

    R. Xu and A. Faragó,The landscape of minimum label cut (hedge connectivity) problemAvailable atarXiv:1908.06541 [cs.DS]

    1908 arXiv

  44. [52]

    Zhang, J.-Y

    P. Zhang, J.-Y. Cai, L. Tang, and W. Zhao,Approximation and hardness results for label cut and related problems, Journal of Combinatorial Optimization21(2): 192–208, 2011. 30

    2011

Pith tools

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