Pith. sign in

REVIEW 3 major objections 4 minor 51 references

Faster Edge Coloring by Partition Sieving

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Edge Coloring and List Edge Coloring can be solved exactly in O*(2^{m−3n/5}) time using only polynomial space, the first faster-than-2^m algorithms for these problems to do so.

desk verdict Resolves a real open question with a genuinely new technique; the only real problem is a fixable typo in Lemma 4.1, and the paper deserves a rigorous but fair referee. read the letter →

arxiv 2501.05570 v1 pith:5SNC7S7M submitted 2025-01-09 cs.DS

Shyan Akmal , Tomohiro Koana This is my paper · ORCID
classification cs.DS MSC 05C1505C7005B3568Q25
keywords edgecoloringchromaticindexlistexactexponentialalgorithmspolynomialspacepartitionsievingPfaffiandominatingset
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

Edge Coloring — deciding whether a graph's edges can be colored with Δ colors, where Δ is the maximum degree — is NP-hard, and previous exact algorithms either ran in O*(2^m) time with polynomial space or ran faster only with exponential space. This paper gives a randomized, one-sided-error algorithm that runs in O*($2^{{m−3n/5}}$) time and polynomial space, and extends the same bound to the harder List Edge Coloring problem. These are the first algorithms for either problem that are simultaneously faster than O*(2^m) and use only polynomial space. The speed-up comes from a new monomial-detection technique called partition sieving, applied to a Pfaffian-based polynomial that encodes tuples of matchings.

What carries the argument

The main object is the polynomial P = Pf(BA B^T), built from a block-diagonal skew-symmetric matrix A that assigns a variable to each edge–color pair and from a matrix B representing a matroid whose ranks encode vertex degrees; by the Ishikawa–Wakayama formula, monomials of P enumerate k-tuples of matchings whose combined vertex incidences match the degree sequence. The runtime engine is partition sieving: if a polynomial P is compatible with a partition matroid having p parts, a multilinear monomial whose support is a basis can be detected in O*($2^{{deg P − p}}$) time and polynomial space, improving the O*($2^{{deg P}}$) of prior basis sieving. The partition is obtained from a dominating set D: each vertex outside D gives one part, so p = n − |D|, and the existence of dominating sets of size at most 2n/5 in minimum-degree-two graphs yields the m − 3n/5 exponent.

What would settle it

Expand the polynomial Pf(BA B^T) from Section 4 on K_4 with k=3 and uniform matroids of rank 3 for each vertex. The tuple M_1=M_2={uv,xy}, M_3={ux,vy} meets the degree constraints defining the collection C, so the expansion must contain a monomial with x_{uv}^2 x_{xy}^2; finding that monomial would refute the squarefree product stated in Lemma 4.1 and force the multiset reading the rest of the proof relies on.

Watch

Extended reading notes

Core claim

The paper's central claim is that the classical question of whether a graph's edges split into Δ matchings can be answered algebraically in O*($2^{{m−3n/5}}$) time, with high probability and one-sided error, using only polynomial space. The same method solves List Edge Coloring, where each edge has a list of allowed colors, in the same time bound. In graphs of average degree d the exponent becomes (1−6/(5d))m, and for d-regular graphs with d≥6 the exponent improves further to m−α_d n with α_d = 1−H_{d+1}/(d+1), approaching m−n as d grows. The proof constructs a polynomial whose multilinear monomials correspond exactly to proper Δ-colorings, then detects such a monomial by sieving over a partition matroid derived from a small dominating set.

Load-bearing premise

The whole speed-up depends on the Pfaffian polynomial recording each edge with multiplicity equal to the number of matchings containing it, because only then does the compatibility step that makes partition sieving apply go through.

Editorial extensions

If this is right

  • If the bound is correct, Edge Coloring in graphs of average degree d runs in O*(2^{(1−6/(5d))m}) time, replacing the previous exponential-space bound with exponent (1/d)^{Θ(d^3)}.
  • List Edge Coloring is solvable in O*(2^{m−3n/5}) time and polynomial space; when all lists draw from k colors, this gives O*(2^{(1−6/(5k))m}) time.
  • For d-regular graphs with d≥6, the exponent improves to m−α_d n with α_d = 1−H_{d+1}/(d+1), so for large degree the runtime approaches O*(2^{m−n}).
  • The framework turns improved dominating-set bounds directly into faster coloring algorithms: any graph class with dominating sets of size at most c n for c<2/5 would immediately give an O*(2^{m−(1−c)n}) algorithm under the same machinery.
  • A vertex of degree one can be deleted without changing whether a Δ-coloring exists, so the core algorithm only needs to handle minimum-degree-two graphs.

Reading between the lines

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

  • The partition-sieving speed-up from 2^d to 2^{d−p} is stated for arbitrary polynomials compatible with a partition matroid; if it extends to other polynomial encodings, the same technique could give faster exact algorithms for other packing and covering problems whose solutions can be enumerated with degree constraints.
  • The paper's bottleneck is the 2n/5 dominating-set bound; if degree-two vertices could be removed as freely as degree-one vertices, the known 3n/8 bound for minimum-degree-three graphs would improve the exponent to m−5n/8 — a direction the authors note in their conclusion.
  • A concrete stress test of the proof is to symbolically expand the Pfaffian on small instances to check the multiset reading of Lemma 4.1; such a check would clarify which version of the encoding lemma the later compatibility argument requires.
  • The extension-matroid construction used for List Edge Coloring turns the star of unit-degree neighbors at each vertex into a matroid constraint, an idea that may transfer to other extension problems where a partial coloring must be extended to a low-degree subgraph.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper introduces a technique called partition sieving, which extends prior determinantal sieving to detect multilinear monomials in a polynomial P that are bases of a partition matroid in O*(2^{d-p}) time and polynomial space, where d is the degree and p is the number of partition classes. It applies this to Edge Coloring and List Edge Coloring by constructing a Pfaffian-based polynomial whose monomials enumerate tuples of matchings with prescribed vertex-degree multiplicities, then using dominating sets to define a compatible partition matroid. The main results are randomized O*(2^{m-3n/5}) time and polynomial-space algorithms for both problems, with an improved bound for regular graphs and a simpler O*(2^{m-3n/5}) bound for list coloring after a tree-pruning reduction.

Significance. If the technical issues identified below are repaired, these would be the first algorithms for Edge Coloring and List Edge Coloring that run in faster than O*(2^m) time while using only polynomial space, which is a substantial improvement over the previous state of the art. The partition sieving theorem (Theorem 3.5) is a clean, parameter-free contribution to algebraic monomial-detection techniques, and the extension-matroid construction for handling low-degree vertices in list edge coloring is elegant. The paper is largely well organized, with concrete runtime bounds and a clear separation between the edge-coloring and list-edge-coloring proofs. The central ideas are plausible and the remaining issues are local, but they are load-bearing and require correction before the proofs can be considered complete.

major comments (3)
  1. [Section 4.1, Lemma 4.1] The displayed formula in Lemma 4.1 writes the X-factor as the squarefree product over M_1 ∪ ... ∪ M_k, but the Pfaffian expansion via Proposition 2.8 and equation (3) yields a factor x_e whose exponent is the number of matchings M_i containing e. The squarefree statement is false for any tuple in C with overlapping matchings, and the compatibility proof in Claim 4.3 depends on the degree of a monomial on edges incident to v being deg_G(v), which is only correct under the multiset reading. The statement should be corrected to use ∏_{i∈[k]} ∏_{e∈M_i} x_e, and the proof of Lemma 4.1 should be adjusted accordingly; with that correction, the subsequent arguments in Lemma 4.2 go through.
  2. [Section 6, Lemma 6.6 and Theorem 1.3] Lemma 6.6 is stated for graphs with n1 unit-degree vertices, but its proof uses mnew = m - n1 and nnew = n - n1, which hold only after the tree-pruning reduction of Section 6.1 has been applied, so that the vertices deleted to obtain Gnew are exactly the unit-degree vertices. The proof of Theorem 1.3 in the case n1 ≥ n/5 should explicitly say that the pruning is performed first, and should then show that the runtime O*(2^{m* - (n*+n1*)/2}) on the pruned graph is at most O*(2^{m-3n/5}) in the original parameters. As written, the application of Lemma 6.6 to the original unpruned graph is not justified.
  3. [Section 6, Theorem 1.3 proof, second case] The proof writes V' = V\D, but when Lemma 4.2 is applied to the polynomial built from Gnew, the relevant partition size is |Vnew\D|, not |V\D|. Moreover, the inequality 'Since mnew ≤ m' is too weak to conclude O*(2^{m-3n/5}); the intended argument should use mnew = m - n1 and |Vnew\D| ≥ 3(n - n1)/5, which gives the stated bound after simplification.
minor comments (4)
  1. [Section 2 and Section 4.1] The symbol W is used both for the disjoint union of vertex copies and for the direct-sum matroid in equation (4); renaming one of these would avoid confusion.
  2. [Section 4.1, Lemma 4.1 proof] There is a typo: 'nonzeo' should be 'nonzero'.
  3. [Section 5, Theorem 1.1 proof] The phrase 'outEdge Coloring algorithms' should be 'our Edge Coloring algorithms'.
  4. [Section 6.1] The uniqueness of the connecting edge e from a tree T_v to v is used implicitly in the discussion of (T_v + e); it would be helpful to state explicitly that a component of G[V1] has at most one edge to any vertex of Gnew, since otherwise (T_v + e) need not be a tree.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the runtime improvement follows from a new partition-sieving theorem and external dominating-set bounds; the cited prior sieving results are used as published lemmas, not as the conclusion of this paper.

full rationale

The derivation chain is self-contained. The central equivalences (Lemma 5.2 for Edge Coloring and Lemma 6.5 for List Edge Coloring) are proven directly from the Pfaffian expansion of P = Pf(BAB^T) and the definitions of the matroids, not assumed as input. The claimed speedup is obtained from the new partition-sieving theorem (Theorem 3.5), whose proof is given in this paper and uses the published odd-sieving lemma of [18]; although [18] is co-authored by Koana, it is an external SODA 2024 theorem cited as a black box, and the compatibility argument is an independent derivation rather than a restatement of the target result. The dominating-set bounds in Lemmas 2.2 and 2.3 are external graph-theoretic facts, and Lemma 2.4 is proved in Appendix C; the runtime O*(2^{m-3n/5}) is obtained by substituting the bound |D| <= 2n/5 into the proved O*(2^{m-|V'|}) template, so no fitted parameter is renamed as a prediction. I also checked the one written gap noted in the manuscript: the displayed formula in Lemma 4.1 writes a squarefree product over the union of matchings, while the Pfaffian expansion produces x_e with multiplicity equal to the number of matchings containing e; taken verbatim this would invalidate the degree computation in Claim 4.3. This is a local correctness error, repairable by using the multiset product, and it is not a circularity because the claimed equivalence is not an input to the construction. No step in the derivation reduces to its own output, so the circularity score is 0.

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

No free parameters are fitted; the field size is set to poly(n) only to make Schwartz-Zippel error small. The new 'partition sieving' is an algorithmic technique, not a postulated entity. The central claim rests on standard external theorems, not on assumptions that encode the answer.

assumptions (5)
  • standard math Ishikawa-Wakayama minor summation formula for Pfaffians
    Used in Lemma 4.1 to expand Pf(BAB^T) as a sum over bases of the matroid W; cited to [25].
  • standard math Determinantal sieving and odd sieving theorems
    Used as black-box (Lemmas 3.3 and 3.4) from [18]; the new partition sieving theorem reduces to odd sieving.
  • domain assumption Dominating set bound: min-degree-2 graphs with n>=8 have a dominating set of size at most 2n/5
    External result [38] stated as Lemma 2.2 and used in Theorems 1.1 and 1.3.
  • standard math Matroids and their linear representations over large finite fields
    Uniform, partition, transversal, dual, and truncation matroid representations are cited standard results (Props 2.9-2.11, B.1-B.3).
  • domain assumption Input graph is connected without loss of generality
    Section 2: solving each connected component separately; the runtime exponent is additive across components.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Edge Coloring by Partition Sieving." pith.science (2026). https://pith.science/paper/5SNC7S7M

@misc{pith2026250105570,
  author       = {Pith},
  title        = {Pith review of: Faster Edge Coloring by Partition Sieving},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5SNC7S7M}},
  note         = {Machine review of arXiv:2501.05570}
}
abstract

In the Edge Coloring problem, we are given an undirected graph $G$ with $n$ vertices and $m$ edges, and are tasked with finding the smallest positive integer $k$ so that the edges of $G$ can be assigned $k$ colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in $2^m\text{poly}(n)$ time and polynomial space, and in graphs with average degree $d$ in $2^{(1-\varepsilon_d)m}\text{poly}(n)$ time and exponential space, where $\varepsilon_d = (1/d)^{\Theta(d^3)}$. We present an algorithm that solves Edge Coloring in $2^{m-3n/5}\text{poly}(n)$ time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than $2^m\text{poly}(m)$ time and uses only polynomial space. In graphs of average degree $d$, our algorithm runs in $2^{(1-6/(5d))m}\text{poly}(n)$ time, which has far better dependence in $d$ than previous results. We also generalize our algorithm to solve a problem known as List Edge Coloring, where each edge $e$ in the input graph comes with a list $L_e\subseteq\left\{1, \dots, k\right\}$ of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We solve this problem in $2^{(1-6/(5k))m}\text{poly}(n)$ time and polynomial space. The previous best algorithm for List Edge Coloring took $2^m\text{poly}(n)$ time and space.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 50 canonical work pages

  1. [1]

    Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices

    Vladimir I Arnautov. Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices. Prikl. Mat. i Programmirovanie , 11(3-8):126, 1974

    work page 1974

  2. [2]

    Vizing's theorem in near-linear time, 2024

    Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, and Tianyi Zhang. Vizing's theorem in near-linear time, 2024

    work page 2024

  3. [3]

    Distributed edge coloring in time polylogarithmic in

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time polylogarithmic in . In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing , PODC ’22, page 15–25. ACM, July 2022

    work page 2022

  4. [4]

    Derived graphs and digraphs

    Lowell W Beineke. Derived graphs and digraphs. Beitr \"a ge zur graphentheorie , pages 17--33, 1968

    work page 1968

  5. [5]

    A fast distributed algorithm for ( +1) -edge-coloring

    Anton Bernshteyn. A fast distributed algorithm for ( +1) -edge-coloring. Journal of Combinatorial Theory, Series B , 152:319–352, January 2022

    work page 2022

  6. [6]

    Arboricity-Dependent Algorithms for Edge Coloring

    Sayan Bhattacharya, Mart \' n Costa, Nadav Panski, and Shay Solomon. Arboricity-Dependent Algorithms for Edge Coloring . In Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) , volume 294 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 12:1--12:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl -- ...

    work page 2024

  7. [7]

    Determinant sums for undirected H amiltonicity

    Andreas Bj \" o rklund. Determinant sums for undirected H amiltonicity. SIAM Journal on Computing , 43(1):280--299, 2014

    work page 2014

  8. [8]

    Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

    Andreas Bj \" o rklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, and Kevin Pratt. Chromatic number in 1.9999^n time? fast deterministic set partitioning under the asymptotic rank conjecture. CoRR , abs/2404.04987, 2024

    work page Pith review arXiv 2024

Show all 51 references
  1. [9]

    Exact algorithms for exact satisfiability and number of perfect matchings

    Andreas Bj\" o rklund and Thore Husfeldt. Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica , 52(2):226–249, December 2007

    2007

  2. [10]

    Trimmed moebius inversion and graphs of bounded degree

    Andreas Bj\" o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Trimmed moebius inversion and graphs of bounded degree. Theory of Computing Systems , 47(3):637–654, January 2009

    2009

  3. [11]

    Narrow sieves for parameterized paths and packings

    Andreas Bj \" o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences , 87:119--139, 2017

    2017

  4. [12]

    Set partitioning via inclusion-exclusion

    Andreas Bj \" o rklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing , 39(2):546--563, 2009

    2009

  5. [13]

    An estimate of the external stability number of a graph without suspended vertices

    M Blank. An estimate of the external stability number of a graph without suspended vertices. Prikl. Mat. i Programmirovanie , 10:3--11, 1973

    1973

  6. [14]

    Enumerating maximal independent sets with applications to graph colouring

    Jesper Makholm Byskov. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters , 32(6):547–556, November 2004

    2004

  7. [15]

    Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-Parameterised Dynamic Edge Colouring . In Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) , volume 294 of Leibniz International Proceedings in Informatics ...

    2024

  8. [16]

    Golovach, Dieter Kratsch, Mathieu Liedloff, and Artem V

    Jean - Fran c ois Couturier, Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, and Artem V. Pyatkin. Colorings with few colors: Counting, enumeration and combinatorial bounds. Theory Comput. Syst. , 52(4):645--667, 2013

    2013

  9. [17]

    Dynamic Edge Coloring with Improved Approximation , page 1937–1945

    Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic Edge Coloring with Improved Approximation , page 1937–1945. Society for Industrial and Applied Mathematics, January 2019

    1937

  10. [18]

    Determinantal sieving

    Eduard Eiben, Tomohiro Koana, and Magnus Wahlstr \" o m. Determinantal sieving. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms ( SODA 2024) , pages 377--423. SIAM , 2024

    2024

  11. [19]

    Small Maximal Independent Sets and Faster Exact Graph Coloring , page 462–470

    David Eppstein. Small Maximal Independent Sets and Faster Exact Graph Coloring , page 462–470. Springer Berlin Heidelberg, 2001

    2001

  12. [20]

    Serge Gaspers and Edward J. Lee. Faster graph coloring in polynomial space. Algorithmica , 85(2):584--609, 2023

    2023

  13. [21]

    Kulikov, and Ivan Mihajlin

    Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. Families with infants: Speeding up algorithms for NP -hard problems using FFT . ACM Trans. Algorithms , 12(3):35:1--35:17, 2016

    2016

  14. [22]

    David G. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019) , pages 700--724, 2019

    2019

  15. [23]

    Michael A. Henning. Bounds on domination parameters in graphs: a brief survey. Discuss. Math. Graph Theory , 42(3):665--708, 2022

    2022

  16. [24]

    The NP -completeness of edge-coloring

    Ian Holyer. The NP -completeness of edge-coloring. SIAM Journal on Computing , 10(4):718--720, 1981

    1981

  17. [25]

    Minor summation formula of pfaffians

    Masao Ishikawa and Masato Wakayama. Minor summation formula of pfaffians. Linear and Multilinear algebra , 39(3):285--305, 1995

    1995

  18. [26]

    Faster algorithms on linear delta-matroids

    Tomohiro Koana and Magnus Wahlstr \"o m. Faster algorithms on linear delta-matroids. arXiv preprint arXiv:2402.11596 , 2024

    2024 arXiv

  19. [27]

    Improved edge-coloring with three colors

    Lukasz Kowalik. Improved edge-coloring with three colors. Theor. Comput. Sci. , 410(38-40):3733--3742, 2009

    2009

  20. [28]

    Tight Lower Bounds for List Edge Coloring

    Lukasz Kowalik and Arkadiusz Socala. Tight Lower Bounds for List Edge Coloring . In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) , volume 101 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 28:1--28:12, ...

    2018

  21. [29]

    If edge coloring is hard under SETH , then SETH is false

    Alexander S Kulikov and Ivan Mihajlin. If edge coloring is hard under SETH , then SETH is false. In 2024 Symposium on Simplicity in Algorithms ( SOSA ) , pages 115--120. Society for Industrial and Applied Mathematics, Philadelphia, PA, January 2024

    2024

  22. [30]

    Eugene L. Lawler. A note on the complexity of the chromatic number problem. Inf. Process. Lett. , 5(3):66--67, 1976

    1976

  23. [31]

    Structure and hardness in P (dagstuhl seminar 16451)

    Moshe Lewenstein, Seth Pettie, and Virginia Vassilevska Williams . Structure and hardness in P (dagstuhl seminar 16451). Dagstuhl Reports , 6(11):1--34, 2016

    2016

  24. [32]

    Deterministic truncation of linear matroids

    Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. ACM Transactions on Algorithms , 14(2):14:1--14:20, 2018

    2018

  25. [33]

    Coverings and colorings of hypergraphs

    L \'a szl \'o Lov \'a sz. Coverings and colorings of hypergraphs. Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing , pages 3--12, 1973

    1973

  26. [34]

    On the hardness of approximating minimization problems

    Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM , 41(5):960–981, September 1994

    1994

  27. [35]

    Odile Marcotte and Paul D. Seymour. Extending an edge-coloring. J. Graph Theory , 14(5):565--573, 1990

    1990

  28. [36]

    List edge multicoloring in graphs with few cycles

    D \' a niel Marx. List edge multicoloring in graphs with few cycles. Inf. Process. Lett. , 89(2):85--90, 2004

    2004

  29. [37]

    A parameterized view on matroid optimization problems

    D \'a niel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science , 410(44):4471--4479, 2009

    2009

  30. [38]

    Domination in graphs with minimum degree two

    William McCuaig and Bruce Shepherd. Domination in graphs with minimum degree two. Journal of Graph Theory , 13(6):749--762, 1989

    1989

  31. [39]

    3-coloring in time O(1.3217^n) , 2023

    Lucas Meijer. 3-coloring in time O(1.3217^n) , 2023

    2023

  32. [40]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, August 1995

    1995

  33. [41]

    Matrices and matroids for systems analysis , volume 20

    Kazuo Murota. Matrices and matroids for systems analysis , volume 20. Springer Science & Business Media, 1999

    1999

  34. [42]

    Theory of graphs

    Oystein Ore. Theory of graphs. In Colloquium Publications . American Mathematical Society, 1962

    1962

  35. [43]

    Matroid Theory

    James Oxley. Matroid Theory . Oxford University Press, 2011

    2011

  36. [44]

    Sur le nombre d'absorption d'un graphe simple

    Charles Payan. Sur le nombre d'absorption d'un graphe simple. 1975

    1975

  37. [45]

    Bruce A. Reed. Paths, stars and the number three. Comb. Probab. Comput. , 5:277--295, 1996

    1996

  38. [46]

    Johan M. M. van Rooij and Hans L. Bodlaender. Exact algorithms for dominating set. Discret. Appl. Math. , 159(17):2147--2164, 2011

    2011

  39. [47]

    Abusing the T utte matrix: An algebraic instance compression for the K -set-cycle problem

    Magnus Wahlstr \" o m. Abusing the T utte matrix: An algebraic instance compression for the K -set-cycle problem. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science ( STACS 2013) , volume 20 of LIPIcs , pages 341--352. Schloss Dagstuh...

    2013

  40. [48]

    Finding paths of length k in O^*(2^k) time

    Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letter , 109(6):315--318, 2009

    2009

  41. [49]

    A Faster Algorithm for the 4-Coloring Problem

    Pu Wu, Huanyu Gu, Huiqin Jiang, Zehui Shao, and Jin Xu. A Faster Algorithm for the 4-Coloring Problem . In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms (ESA 2024) , volume 308 of Leibniz International P...

    2024

  42. [50]

    Breaking the 2^n barrier for 5-coloring and 6-coloring

    Or Zamir. Breaking the 2^n barrier for 5-coloring and 6-coloring. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming ( ICALP 2021) , volume 198 of LIPIcs , pages 113:1--113:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

    2021

  43. [51]

    Algorithmic applications of hypergraph and partition containers

    Or Zamir. Algorithmic applications of hypergraph and partition containers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing ( STOC 2023) , pages 985--998. ACM , 2023

    2023

Pith tools

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