Fact-checked by Grok 2 weeks ago

Graph factorization

Graph factorization is a core concept in graph theory involving the decomposition of a graph's edge set into spanning subgraphs called factors, where a factor is defined as a subgraph that includes all vertices of the original graph but may have a subset of its edges.^[1]^[2] A factorization partitions the edges into such factors, typically with constraints on vertex degrees or structural properties to ensure disjoint coverage.^[1] This framework extends to specific types, such as k-factors, which are regular spanning subgraphs where every vertex has degree exactly k.^[2] Key subtypes include the 1-factor, or perfect matching, which pairs all vertices with no shared edges, and the 2-factor, a 2-regular spanning subgraph consisting of disjoint cycles covering every vertex.^[1] Factorizations often target these structures; for instance, a 1-factorization decomposes the graph into edge-disjoint perfect matchings, while a 2-factorization partitions into 2-factors.^[2] Existence conditions are governed by foundational theorems: Tutte's 1-factor theorem states that a graph has a 1-factor if and only if for every subset S of vertices, the number of odd components in the graph minus S is at most the size of S.^[1] In bipartite graphs, Hall's marriage theorem guarantees a 1-factor if for every subset A of one part, the neighborhood N(A) satisfies |N(A)| ≥ |A|.^[1] Regular graphs, such as complete graphs K_2n and bipartite complete graphs K_{n ,n}, admit 1-factorizations under specific conditions.^[2] Beyond basic decompositions, graph factorization encompasses broader variants like degree factors (prescribed degrees per vertex) and component factors (e.g., path or star factors with defined component types).^[1] Petersen's theorem ensures that every 2-edge-connected cubic multigraph has a 1-factor, aiding in decompositions of 3-regular graphs.^[1] For 2-factorizations, complete graphs K_2n+1 decompose into n Hamiltonian cycles, and bridgeless cubic graphs can be expressed as the union of a 1-factor and a 2-factor.^[2] The Nash-Williams theorem on arboricity provides a measure for the minimum number of forests needed to cover the edges, linking to acyclic factorizations via max{e_H / (v_H – 1)} over subgraphs H.^[2] Applications of graph factorization span combinatorial design, where it models resolvable block designs and tournament scheduling; network flows, for edge-disjoint path decompositions; and optimization problems like edge coloring, where the chromatic index equals the maximum degree for class-1 graphs admitting 1-factorizations.^[1] It also informs Hamiltonian cycle detection, statistical analysis of relational data, and parallel computing architectures.^[1] These decompositions highlight the structural richness of graphs, with ongoing research exploring generalizations to directed graphs, hypergraphs, and weighted settings.^[1]

Definitions

Factors and k-Factors

In graph theory, a subgraph of a graph G is obtained by deleting some vertices and edges from G, while preserving the incidences between the remaining vertices and edges.^[3] A spanning subgraph, in particular, includes all vertices of G but possibly only a subset of its edges.^[3] A factor of a graph G is defined as a spanning subgraph of G.^[1] More specifically, a k-factor of G is a spanning k-regular subgraph, where every vertex in the subgraph has degree exactly k.^[4] A graph is k-regular if every vertex has degree k.^[5] Special cases of k-factors include the 1-factor and 2-factor. A 1-factor is a 1-regular spanning subgraph, which is equivalent to a perfect matching that covers every vertex of G exactly once.^[6] A 2-factor is a 2-regular spanning subgraph, consisting of a vertex-disjoint union of cycles that together include all vertices of G.^[7] For example, the complete graph K_3 on three vertices has no 1-factor, as it contains an odd number of vertices and thus cannot admit a perfect matching.^[6] In contrast, the complete graph K_4 on four vertices does possess a 1-factor, such as the matching formed by two non-adjacent edges.^[6]

Factorizations

A k-factorization of a graph G is a partition of the edge set E(G) into edge-disjoint k-factors, where each k-factor is a spanning k-regular subgraph of G.^[8] This decomposition ensures that every edge of G belongs to exactly one k-factor in the partition, and the union of all k-factors reconstructs G completely.^[9] For a graph G to admit a k-factorization into m such factors, G must be d-regular with d = k m, meaning the degree d is a multiple of k and the factorization consists of exactly d/k factors.^[10] This regularity condition arises because each vertex in G has degree d, and in the partition, it must achieve degree exactly k in each of the m = d/k factors.^[8] The concept of graph factorization traces its origins to Julius Petersen's 1891 paper on the decomposition of regular graphs, where he introduced the idea in the context of partitioning into 2-factors.^[11] In the specific case of k=1, a 1-factorization of a \Delta-regular graph of even order exists if and only if the graph is class 1, meaning its chromatic index equals its maximum degree \Delta.^[12] Such a 1-factorization is equivalent to a proper edge coloring with \Delta colors, where each color class forms a perfect matching.^[13] For example, the complete graph K_{2n}, which is (2n-1)-regular on $2n vertices, admits a 1-factorization into $2n-1 perfect matchings.^[14]

1-Factorization

Complete Graphs

The complete graph K_{2n} of even order $2n admits a 1-factorization consisting of $2n-1 edge-disjoint perfect matchings, each covering all $2n vertices.^[15] A standard explicit construction, attributed to Walecki from the 1890s, uses a geometric or rotational method. Place $2n-1 vertices labeled $0, 1, \dots, 2n-2 at the vertices of a regular (2n-1)-gon and the remaining vertex, denoted \infty, at the center. The initial perfect matching pairs \infty with $2n-2, and connects i to i+1 \pmod{2n-1} for i = 0 to n-2, with the opposite pairs adjusted to form parallel chords or diameters in the polygon. Subsequent matchings are obtained by rotating this initial matching by multiples of $360^\circ / (2n-1). For example, in K_4 (n=2), label vertices \infty, 0, 1, 2; one matching is \{\infty-2, 0-1\}, and the other two are rotations thereof, yielding the full 1-factorization.^[16]^[17] The number of distinct 1-factorizations of K_{2n} has known values including 1 for n=1, 1 for n=2, 6 for n=3, and 6240 for n=4. This structure finds application in scheduling round-robin tournaments with $2n teams, where each 1-factor corresponds to a round of n simultaneous matches, ensuring every team plays exactly once per round across $2n-1 rounds.^[18] In contrast, the complete graph K_{2n+1} of odd order $2n+1 admits no 1-factorization, as it lacks even a single perfect matching due to the odd number of vertices. However, it possesses a near 1-factorization into $2n+1 edge-disjoint near 1-factors, where each near 1-factor is a matching covering $2n vertices and leaving one uncovered, with every edge appearing in exactly one such factor.^[19]

1-Factorization Theorem

The 1-factorization conjecture states that every d-regular graph G of even order n=2m with d \geq m admits a 1-factorization, meaning its edges can be partitioned into d perfect matchings.^[20] Equivalently, such a graph has chromatic index \chi'(G) = \Delta(G) = d, classifying it as a class 1 graph.^[20] This conjecture implies that regular graphs of sufficiently high degree are 1-factorizable, providing a sharp threshold for the existence of such decompositions.^[21] Proposed by Chetwynd and Hilton in 1985, the conjecture built on earlier partial results, such as their own proof that d \geq \lceil 6n/7 \rceil suffices for 1-factorizability. Subsequent advancements included further improvements by various authors narrowing the gap to the conjectured threshold. The conjecture remained open for decades until a major breakthrough by Csaba, Kühn, Lo, Osthus, and Treglown, who proved it holds for all sufficiently large n using probabilistic methods, including the blow-up lemma and robust expanders to ensure the existence of near-perfect matchings that can be iteratively extended.^[21] A related result is that every regular bipartite graph has chromatic index equal to its degree, by König's theorem, implying 1-factorizability regardless of the degree parity.^[21] Vizing's theorem more generally classifies simple graphs as having \chi'(G) = \Delta(G) or \Delta(G)+1, but does not guarantee class 1 status for non-bipartite regular graphs of even degree; counterexamples exist, such as the odd complete graph K_{2m+1}, which is $2m-regular (even degree) but class 2 with \chi'(K_{2m+1}) = 2m+1. For small cases below the threshold, counterexamples include the [Petersen graph](/page/Petersen_graph), a 3-regular graph on 10 vertices (d=3 < 5 = n/2$) that is class 2 and lacks a 1-factorization.

Perfect 1-Factorization

A perfect 1-factorization of a regular graph of even order is a 1-factorization in which the union of every pair of distinct 1-factors forms a single Hamiltonian cycle.^[17] This property distinguishes perfect 1-factorizations from ordinary ones by imposing the additional condition that pairwise unions are connected and spanning cycles, rather than potentially disjoint cycles.^[22] The existence of perfect 1-factorizations for complete graphs K_{2n} (with n \geq 2) was conjectured by Anton Kotzig in 1963, positing that such a factorization exists for every even order.^[23] Constructions are known for the infinite family of K_{2p} where p is an odd prime, independently developed by Ian Anderson and M. Nakamura using methods involving finite fields.^[24] Perfect 1-factorizations also exist for specific even orders beyond this family, including K_8, K_{14}, and K_{18}.^[25] A key property of a perfect 1-factorization is that it generates \binom{2n-1}{2} distinct Hamiltonian cycles in K_{2n}, one for each pair of 1-factors, providing a structured way to decompose pairs of matchings into cycles while the full set partitions the edges.^[17] This orthogonality to standard 1-factorizations arises solely from the Hamiltonian condition on pairs, enabling applications in design theory and scheduling where cycle connectivity is required.^[22] The Kotzig conjecture remains open, though perfect 1-factorizations are known to exist for all even orders up to 56 and for additional specific larger orders such as 58, 60, 62, 68, 72, 74, 80, and 82.^[23]^[17] For K_6, every 1-factorization is perfect, serving as a small example where the condition holds universally despite the graph's modest size.^[17]

2-Factorization

Existence Theorems

A fundamental result in graph factorization is Petersen's theorem, which establishes the existence of a 2-factorization for regular graphs of even degree. Specifically, every 2k-regular multigraph admits a decomposition into k edge-disjoint 2-factors. This theorem, proved by Julius Petersen in 1891, applies to both simple graphs and multigraphs, ensuring that the edge set can be partitioned into spanning 2-regular subgraphs, each consisting of disjoint cycles covering all vertices.^[11] The proof proceeds by induction on k. For the base case k=1, the 2-regular multigraph is itself a 2-factor. For the inductive step, a 2-factor is constructed in the 2k-regular multigraph by leveraging Eulerian paths: consider an Eulerian orientation where each vertex has equal in- and out-degree k, then decompose the directed graph into directed cycles, and take the underlying undirected cycles to form the 2-factor; removing this 2-factor leaves a (2k-2)-regular multigraph, to which the inductive hypothesis applies.^[26] Extensions of this result address the structure of the 2-factors in connected 2k-regular graphs. Under additional conditions, such as sufficient connectivity, each 2-factor in the decomposition can be required to be Hamiltonian (a single cycle spanning all vertices). For example, the cycle graph C_{2k} is 2-regular and trivially admits a 2-factorization into one copy of itself as the sole 2-factor, while non-trivial decompositions arise in complete graphs like K_{2m+1}, which is 2m-regular and decomposes into m Hamiltonian 2-factors.^[27] This existence result connects to broader Hamiltonicity criteria in regular graphs.

Oberwolfach Problem

The Oberwolfach problem asks whether, for a positive integer m, the complete graph K_{2m+1} admits a 2-factorization into m isomorphic 2-factors, each a Hamilton cycle on 2m+1 vertices. Generalized versions of the problem consider directed complete graphs or multigraphs, where the decomposition must respect the directed edges or multiple edges between vertices.^[28] The problem originated at a 1967 conference on combinatorial theory held at the Mathematisches Forschungsinstitut Oberwolfach in Germany, where it was posed by Gerhard Ringel in the context of seating arrangements that ensure every pair of participants sits together exactly once over multiple meals. For the case of Hamilton cycles, the problem is completely solved: every complete graph K_{2m+1} (m ≥ 1) admits such a decomposition, via explicit constructions such as Walecki's method.^[29] For example, when n=5 and k=2 (i.e., m=2), K_5 admits a decomposition into two 5-cycles: label the vertices 1 through 5, with one cycle given by (1-2-3-4-5) and the complementary cycle by (1-3-5-2-4). This construction extends the known full Hamilton decomposition of K_5, which covers all edges.^[29]

Higher k-Factorizations

General Theorems

A regular graph G of degree d admits a k-factorization, for k \geq 3, only if k divides d and, when k is odd, the number of vertices is even, ensuring the sum of degrees in each k-factor is even.^[10] These conditions are necessary because each k-factor must be a spanning k-regular subgraph, so the total degree contribution per vertex across all factors must equal d, and the handshaking lemma requires even degree sums.^[10] Sufficiency holds under additional structural assumptions, such as high edge-connectivity. For odd k \geq 3, if G is r-regular with k dividing r and has odd edge-connectivity at least k(k-1), then G can be decomposed into r/k edge-disjoint k-factors.^[30] When k is even, the condition relaxes to an even number of vertices and edge-connectivity at least k(k-1), yielding the same decomposition.^[30] These connectivity thresholds ensure the existence of balanced spanning subgraphs at each step of the decomposition process.^[30] An adaptation of Baranyai's theorem to graphs provides a specific case for complete graphs. For the complete graph K_n with n-1 divisible by k \geq 3, K_n admits a k-factorization into (n-1)/k isomorphic k-factors, provided n is even when k is odd; this follows as a 2-uniform instance of Baranyai's 1975 result on decomposing complete uniform hypergraphs into 1-factors, specialized via grouping matchings into regular factors.^[31] For k=3, Petersen's 1891 theorem guarantees that every bridgeless 3-regular graph contains a 1-factor, which extends via iterative removal to potential decompositions in higher multiples of 3-regular graphs, though full 3-factorization requires additional conditions like avoiding class-2 structures.^[32] Generalizations of Petersen's result, such as Bäbler's theorem, ensure 2-factors in (2k+1)-regular 2-edge-connected multigraphs for k ≥ 1, providing building blocks for 3-factor constructions in related settings.^[1] Counterexamples illustrate limitations due to connectivity or parity issues. The disjoint union of two copies of K_7 forms a 6-regular graph on 14 vertices, yet lacks a 3-factorization because each component has an odd number of vertices (7), making a 3-regular spanning subgraph impossible in odd order for odd degree.^[33] Such disconnected or low-connectivity regular graphs fail the spanning regularity requirement, highlighting the role of global connectivity in theorems like those based on edge-connectivity bounds.^[33]

Algorithms and Complexity

Finding a 1-factorization of a graph is computationally challenging in general. For small complete graphs, backtracking algorithms can be employed to construct 1-factorizations by systematically building perfect matchings while ensuring no edges are reused, though this approach becomes infeasible for large instances due to exponential time complexity.^[19] In contrast, for regular bipartite graphs, 1-factorizations can be computed efficiently in polynomial time by repeatedly applying bipartite matching algorithms, such as the Hopcroft-Karp algorithm, to extract perfect matchings until all edges are covered; a specialized variant achieves this in O(n \Delta + n \log n) time, where n is the number of vertices and \Delta is the degree.^[34] The decision problem of whether a general graph admits a 1-factorization is NP-complete, even when restricted to cubic graphs, as shown by a reduction from 3-SAT to the edge-coloring problem, which is equivalent for regular graphs.^[35] This hardness holds for fixed degrees d \geq 3, implying no efficient general algorithm exists unless P=NP. However, for bipartite graphs, the equivalence to edge-coloring allows polynomial-time solvability via the aforementioned matching-based methods, leveraging König's theorem that the chromatic index equals the maximum degree.^[34] For 2-factorizations, which decompose the edges into disjoint 2-regular spanning subgraphs (cycle covers), algorithms typically involve iteratively finding a 2-factor and removing its edges. A 2-factor can be computed in polynomial time using maximum matching techniques to ensure degree constraints, followed by cycle detection; for dense graphs like complete graphs K_{2n+1}, constructive methods based on rotational symmetries yield a 2-factorization in O(n^2) time by generating Hamilton cycles systematically.^[1] These approaches exploit the even degree regularity required for existence, partitioning the edge set into n such 2-factors. No general-purpose efficient software solvers exist for higher k-factorizations across arbitrary graphs, though tools like nauty can assist in enumerating small graph structures for verification, and custom backtracking implementations are common for exact solutions in constrained cases. Overall, while theoretical existence theorems guide algorithmic design, computational bottlenecks persist for non-bipartite and high-degree instances.

References

[1]
Graph factors and factorization: 1985–2003: A survey - ScienceDirect
Apr 6, 2007 · A factor of a graph G is just a spanning subgraph of G and a graph factorization of G is a partition of the edges of G into factors.
[2]
[PDF] Factorization - GRAPH THEORY and APPLICATIONS
Theorem: If a 2-connected graph has a 1-factor, then it has at least two different 1-factors. Page 7. Graph Theory and Applications © 2007 A. Yayimli. 7.
[3]
[PDF] Section 2.2. Spanning and Induced Subgraphs
Sep 28, 2020 · Definition. A spanning subgraph of a graph G is a subgraph obtained by edge deletions only (so that a spanning subgraph is a subgraph of G ...
[4]
[PDF] 2-Factors in Graphs - arXiv
Oct 13, 2025 · A k-factor of a graph is a spanning subgraph of that graph in which all vertices have degree k. Graph theory in the form we know it was created ...
[5]
Regular Graph -- from Wolfram MathWorld
A directed graph is called regular if the number of edges incident on each vertex is the same, regardless if the edges are in-edges, out-edges, or both. For ...
[6]
[PDF] Section 16.4. Perfect Matchings and Factors
Feb 7, 2022 · He associated perfect matchings with factors of degree one. For this reason, perfect matchings are also called 1-factors. Pertersen's work ...
[7]
[PDF] 2-factors in Dense Graphs - Princeton Math
A 2-factor of a graph G is a 2-regular spanning subgraph of G, that is, a spanning subgraph every connected component of which is a cycle. In the following ...
[8]
1 Basic Graph Theory
A k-factor is a k-regular spanning subgraph. If the edge set of a graph can be divided into k-factors, such a decomposition is called a k-factorization of the ...
[9]
[PDF] Regular Factors in Graphs
A regular spanning subgraph of degree k is usually called a k- factor, and a graph is called k-factorizable, if its edge set can be decomposed into edge- ...
[10]
[PDF] Factors
Theorem 3 Every k−regular bipartite graph has a 1−factorization. Theorem 4 A graph G has a 2−factorization if and only if G is k−regular for some even k. Proof: ...
[11]
Julius Petersen's theory of regular graphs - ScienceDirect.com
In 1891 the Danish mathematician Julius Petersen (1839–1910) published a paper on the factorization of regular graphs. This was the first paper in the ...Missing: factors | Show results with:factors
[12]
[PDF] The chromatic index of block intersection graphs of Kirkman triple ...
If G is a Δ-regular Class 1 graph of even order, then the edges of G can be parti- tioned into Δ 1-factors (i.e., 1-regular spanning subgraphs); such a ...<|separator|>
[13]
[PDF] The chromatic index of strongly regular graphs - arXiv
Sep 16, 2020 · So being regular and class 1 is the same as having a 1-factorization (being 1-factorable), and requires that the graph has even order. A graph G ...
[14]
On one-factorizations of complete graphs | Request PDF
Aug 6, 2025 · A 1-factorization of K 2n is a proper edge-colouring of K 2n with 2n − 1 colours, or equivalently a decomposition of the edges of K 2n into ...
[15]
One-factorizations of the complete graph - A survey | Semantic Scholar
A 1-factorization is constructed for the line graph of the complete graph Kn when n is congruent to 0 or 1 modulo 4. 13 Citations.Missing: rotation | Show results with:rotation
[16]
[PDF] The-wonderful-Walecki-construction.pdf - ResearchGate
Dec 20, 2006 · In other words, Walecki gives a Hamilton decomposition of complete graphs of even order with a 1-factor removed. We shall denote these graphs by ...
[17]
[PDF] Perfect 1-Factorisations
Theorem (Walecki, 1890s). For each m ⩾ 2, the complete graph K2m has a 1-factorisation. Hence a resolvable (2m,2,1)-BIBD exists for each m ⩾ 2. Slide 8 of 27 ...
[18]
[PDF] Round robin scheduling - a survey
A rich line of research has been to exploit the close relationship between 1-factorizations of graphs with tournaments. When venues are added, this leads to ...
[19]
[PDF] Various One-Factorizations of Complete Graphs - People | MIT CSAIL
Apr 2, 2007 · In this section, we consider incremental methods of constructing an one-factorization of K2n using some heuristics. It can be easily seen ...Missing: K | Show results with:K
[20]
Proof of the 1-factorization and Hamilton Decomposition Conjectures
Jan 16, 2014 · Proof of the 1-factorization and Hamilton Decomposition Conjectures. Authors:Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, Andrew Treglown.
[21]
AMS eBooks: Memoirs of the American Mathematical Society
In this paper we prove the following results (via a unified approach) for all sufficiently large n : [ 1 -factorization conjecture] Suppose that ...
[22]
[PDF] Perfect 1-factorisations of complete k-uniform hypergraphs
A perfect 1-factorisation of a graph has unions of 1-factors isomorphic to the same connected subgraph, connected, and a Hamilton cycle. This is generalized to ...Missing: matchings | Show results with:matchings<|control11|><|separator|>
[23]
[1810.08734] A Perfect One-Factorisation of $K_{56}$ - arXiv
Oct 20, 2018 · In 1963, Anton Kotzig conjectured that for each n \geq 2 the complete graph K_{2n} has a perfect one-factorisation (ie, a decomposition into perfect matchings)Missing: Anderson | Show results with:Anderson<|control11|><|separator|>
[24]
On perfect one-factorization of the complete graphK 2p
Anderson [1, 2] and Nakamura [4] have constructed perfect 1-factorizations ofK 2p independently, wherep is an odd prime. In this paper, we show that these.
[25]
Perfect 1-factorizations | Request PDF - ResearchGate
Aug 7, 2025 · Kotzig conjectured in 1964 that every complete graph on an even number of vertices has a perfect 1-factorization [6]. This conjecture remains ...
[26]
[PDF] Petersen's proof of his theorem
Theorem 1 (Petersen) For every positive integer k, every 2k-regular multigraph can be decomposed into k 2-regular spanning subgraphs. First, Petersen rephrased ...
[27]
[PDF] An updated survey on 2-Factors of Regular Graphs - arXiv
Aug 15, 2024 · We present a survey summarising results on the structure of 2-factors in regular graphs, as achieved by various researchers in recent years.
[28]
[1806.04644] Resolution of the Oberwolfach problem - arXiv
Jun 12, 2018 · The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K_{2n+1} into edge-disjoint copies of a given 2-factor.
[29]
[PDF] Resolution of the Oberwolfach problem - School of Mathematics
Jan 25, 2021 · Abstract. The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K2n+1 into edge-disjoint copies of a given 2-factor.
[30]
On sharply vertex transitive 2-factorizations of the complete graph
We introduce the concept of a 2-starter in a group G of odd order. We prove that any 2-factorization of the complete graph admitting G as a sharply vertex ...
[31]
[PDF] On the Oberwolfach problem for single-flip 2-factors via graceful ...
Oct 14, 2020 · Graceful labelings of zillion graphs with two components were built in [43] set- tling a conjecture posed by Frucht and Salinas [26] in 1985. As ...
[32]
Factorizing regular graphs - ScienceDirect.com
If q is odd and k is even, then we must require that G has an even number of vertices just to guarantee that G has a q-factor. If we want a decomposition into q ...
[33]
Connected Baranyai's theorem | Combinatorica
Feb 8, 2014 · Baranyai showed that K h n can be expressed as the union of edge-disjoint r-regular factors if and only if h divides rn and r divides ( h − 1 n ...
[34]
[PDF] E cient Algorithms for Petersen's Matching Theorem
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores e ...
[35]
existence 3-regualar sub graph in 6- regular graph.
Dec 18, 2020 · I've been struggling to find a counter example for the last half hour. I see no reason to believe a 6-regular connected graph has a 3-factor ...Graph isomorphisms on 6 vertices with degree 3Does any d-regular simple graph G contain a k-regular subgraph ...More results from math.stackexchange.com
[36]
Random regular graphs of high degree - Wiley Online Library
Jun 20, 2001 · Random regular graphs of high degree. Michael Krivelevich,. Michael ... Upfal, Large regular factors in random graphs, in Convexity and ...
[37]
[PDF] Random Regular Graphs of High Degree
Strictly speaking, the term “random graph” comprises several models of random graphs which are quite different in many aspects.
[38]
Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring ...
This paper gives a new and faster algorithm to find a 1-factor in a bipartite Δ -regular graph. The time complexity of this algorithm is O ⁢ ( 𝑛 ⁢ Δ + 𝑛 ⁢ l ...
[39]
The NP-Completeness of Edge-Coloring
By Vizing's theorem [1], the chromatic index is either d or d + 1, where d is the maximum vertex degree.
[40]
[PDF] Improved approximation algorithms for maximum cut and ...
We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions ...