The Factorization of Linear Graphs
From MaRDI portal
Publication:5785127
DOI10.1112/jlms/s1-22.2.107zbMath0029.23301OpenAlexW1985061810WikidataQ61661702 ScholiaQ61661702MaRDI QIDQ5785127
Publication date: 1947
Published in: Journal of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/jlms/s1-22.2.107
Related Items
An Asymptotic Multipartite Kühn--Osthus Theorem, The number of disjoint perfect matchings in semi-regular graphs, Matching of Given Sizes in Hypergraphs, Construction of k-matchings in graph products, Three‐regular subgraphs of four‐regular graphs, A Degree Sequence Strengthening of the Vertex Degree Threshold for a Perfect Matching in 3-Uniform Hypergraphs, On the existence of a factor of degree one of a connected random graph, Pfaffian and decomposable numerical range of a complex skew symmetric matrix, Extremal Graphs With a Given Number of Perfect Matchings, Fractional Matching Preclusion for (n,k)-Star Graphs, Fractional matching, factors and spectral radius in graphs involving minimum degree, Finding Maximum Edge-Disjoint Paths Between Multiple Terminals, Connections between graphs and matrix spaces, Eigenvalues and [a,b‐factors in regular graphs], Graph and hypergraph colouring via nibble methods: a survey, A proof of the Erdős-Faber-Lovász conjecture, Unnamed Item, Some new results on Gallai theorem and perfect matching for \(k\)-uniform hypergraphs, Minimally \(k\)-factor-critical graphs for some large \(k\), Matchings in graphs from the spectral radius, Polyhedral techniques in combinatorial optimization: matchings and tours, A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices, Some sufficient conditions for a graph with minimum degree to be \(k\)-factor-critical, Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints, An improvement on Łuczak's connected matchings method, d-matching in k-uniform hypergraphs, Smith normal form and the generalized spectral characterization of oriented graphs, Resolution of the Erdős–Sauer problem on regular subgraphs, On the structure of factorizable graphs, Unions of perfect matchings in \(r\)-graphs, Complete characterization of path-factor and path-factor covered graphs via Q -index and D -index, Bi-oriented graphs and four valued logic for preference modelling, Hardness of graph-structured algebraic and symbolic problems, Sufficient conditions for matchings, Packing $k$-Matchings and $k$-Critical Graphs, Minimum degree of minimal \((n-10)\)-factor-critical graphs, Binding number, \(k\)-factor and spectral radius of graphs, How many matchings cover the nodes of a graph?, On the rank of a real skew symmetric matrix described by an oriented graph, On matching extendability of lexicographic products, Minimum Codegree Threshold forC63-Factors in 3-Uniform Hypergraphs, Group-theoretic generalisations of vertex and edge connectivities, Matchings in graphs, Unnamed Item, Flows on Signed Graphs without Long Barbells, Unnamed Item, The isolated-pentagon rule and nice substructures in fullerenes, Many Visits TSP Revisited, Properties of hyperprimitive graphs, A Weighted Linear Matroid Parity Algorithm, The hyper-Zagreb index of cacti with perfect matchings, Circular edge-colorings of cubic graphs with girth six, Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs, The binding number of a graph and its Anderson number, Indeterminates and incidence matrices†, Domination critical graphs, On Ramsey minimal graphs, On generalizations of matching-covered graphs, Unnamed Item, Unnamed Item, On the anti-Kekulé problem of cubic graphs, Spectral characterization of matchings in graphs, Matching number, connectivity and eigenvalues of distance signless Laplacians, On factorisation of graphs, On the Chromatic Number of Matching Kneser Graphs, The maximal genus of planar graphs, Unnamed Item, Shortest Two Disjoint Paths in Polynomial Time, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, A Pfaffian formula for matching polynomials of outerplanar graphs, Edge-disjoint Hamilton cycles in random graphs, Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen, Unnamed Item, Surface Embedding of Non-Bipartite $k$-Extendable Graphs, The maximum genus, matchings and the cycle space of a graph, The Monochromatic Circumference of 2‐Edge‐Colored Graphs, Spectral radius and fractional matchings in graphs, The anti-Kekulé number of graphs, Nice pairs of disjoint pentagons in fullerene graphs, Matching preclusion for vertex-transitive networks, Maximum matchings in a class of random graphs, Matching is as easy as matrix inversion, Matchings in infinite graphs, Minimal regular 2-graphs and applications, The circular chromatic index of graphs of high girth, Edge-colouring random graphs, Matching structure and the matching lattice, Graph factors and factorization: 1985--2003: a survey, On factors with given components, On the size of graphs of class 2 whose cores have maximum degree two, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Spanning Eulerian subgraphs and matchings, Smallest close to regular bipartite graphs without an almost perfect matching, The two ear theorem on matching-covered graphs, On the determinant of bipartite graphs, Induced matchings in subcubic graphs without short cycles, Matchings in graphs of odd regularity and girth, On maximum matchings in almost regular graphs, Matching and edge-connectivity in regular graphs, The extendability of matchings in strongly regular graphs, Perfect matchings in 3-partite 3-uniform hypergraphs, On n-extendable graphs, Matroid matching and some applications, Matching signatures and Pfaffian graphs, Matrices of zeros and ones with fixed row and column sum vectors, The characteristic polynomial and the matchings polynomial of a weighted oriented graph, The existence of even regular factors of regular graphs on the number of cut edges, f-factors and related decompositions of graphs, Subgraphs and their degree sequences of a digraph, On generalized matching problems, Hexagonal resonance of (3,6)-fullerenes, Higher-order triangular-distance Delaunay graphs: graph-theoretical properties, Cardinality constrained combinatorial optimization: complexity and polyhedra, The difference and ratio of the fractional matching number and the matching number of graphs, A new linear programming algorithm - better or worse than the simplex method?, Tight bound for matching, Matchings in regular graphs, Variations on a theorem of Petersen, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, Matching preclusion and conditional matching preclusion for regular interconnection networks, Vertex-deleted subgraphs and regular factors from regular graph, A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem, On two-factors of bipartite regular graphs, Matchings and \(\Delta\)-matroids, Combinatorial and computational aspects of graph packing and graph decomposition, Graph factors, One-factor in random graphs based on vertex choice, A new family of finite solutions, Polynomial-time perfect matchings in dense hypergraphs, On the perfect matchings of near regular graphs, Excessive index for mesh derived networks, On saturation games, Chvátal-Erdős type conditions for Hamiltonicity of claw-free graphs, Claw-free graphs. IV: Decomposition theorem, Odd properly colored cycles in edge-colored graphs, Bond graphs. II: Causality and singularity, Max-cut and extendability of matchings in distance-regular graphs, Spanning closed trails in graphs, Packings and perfect path double covers of maximal planar graphs, Extending matchings in planar graphs. IV, Finding a shortest non-zero path in group-labeled graphs via permanent computation, Efficient stabilization of cooperative matching games, On the sextet polynomial of fullerenes, Selected topics on assignment problems, Strongly linear trend-free block designs and 1-factors of representative graphs, The game of \(\mathcal F\)-saturator, Computing large matchings in planar graphs with fixed minimum degree, The perfect matching polytope and solid bricks, On T-joins and odd factors, Spanning trees of 3-uniform hypergraphs, Constructive proof of deficiency theorem of \((g,f)\)-factor, Induced claws and existence of even factors of graphs, On the number of disjoint perfect matchings of regular graphs with given edge connectivity, Conditional matching preclusion sets, Lower bounds of distance Laplacian spectral radii of \(n\)-vertex graphs in terms of matching number, Paths and cycles concerning independence edges, The perfectly matchable subgraph polytope of an arbitrary graph, A simple existence criterion for \((g<f)\)-factors, Degree condition for the existence of a \(k\)-factor containing a given Hamiltonian cycle, Faktorklassen in Graphen, Bounds on maximum \(b\)-matchings, Edge-deletable IM-extendable graphs with minimum number of edges, Linear-time certifying algorithms for near-graphical sequences, Short proofs on the matching polyhedron, Regular graphs and edge chromatic number, Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem, The Edmonds-Gallai decomposition for matchings in locally finite graphs, Regular factors in nearly regular graphs, An extension of matching theory, A generalization of Tutte's 1-factor theorem to countable graphs, On factors with all degrees odd, Toughness and Delaunay triangulations, Chain packing in graphs, Packings by cliques and by finite families of graphs, A degree sequence Hajnal-Szemerédi theorem, Some extremal graphs with respect to inverse degree, Tight bounds on maximal and maximum matchings, A generalisation of matching and colouring, Factors of trees, Characterization of saturated graphs related to pairs of disjoint matchings, Protecting convex sets, Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Line segment visibility with sidedness constraints, Graph-theoretical conditions for inscribability and Delaunay realizability, Binding number and toughness for matching extension, Matching in power graphs of finite groups, Minimum degree, independence number and regular factors, The \(\beta\)-assignment problem in general graphs, Bicritical graphs without removable edges, Quasi-claw-free graphs, Expressions for the perfect matching numbers of cubic \(l\times m\times n\) lattices and their asymptotic values, A generalization of Little's theorem on Pfaffian orientations, Edge coloring of signed graphs, Characterization of 1-tough graphs using factors, An odd \([ 1 , b \)-factor in regular graphs from eigenvalues], Matching connectivity: on the structure of graphs with perfect matchings, \(d\)-matching in 3-uniform hypergraphs, Strong Tutte type conditions and factors of graphs, Strong matching preclusion number of graphs, The total domination subdivision number in graphs with no induced 3-cycle and 5-cycle, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, Forbidden induced subgraphs for perfect matchings, Some results on the inverse sum indeg index of a graph, Matching preclusion number of graphs, Toughness and matching extension in \({\mathcal{P}_3}\)-dominated graphs, On a min--max theorem on bipartite graphs, Trees with 1-factors and oriented trees, On pseudomatroid property of matrices, Perfect matching covers of cubic graphs of oddness 2, The image of weighted combinatorial problems, An introduction to randomized algorithms, Degree conditions of induced matching extendable graphs, The symbiotic relationship of combinatorics and matrix theory, On the tree packing problem, A structure theorem for maximum internal matchings in graphs, Directed star decompositions of directed multigraphs, On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions, Enumerating alternating matrix spaces over finite fields with explicit coordinates, Infinite matching theory, Computing girth and cogirth in perturbed graphic matroids, Detecting cycles through three fixed vertices in a graph, Matching theory -- a sampler: From Dénes König to the present, Perfect matchings and \(K_{1,p}\)-restricted graphs, Structural results on matching estimation with applications to streaming, The cyclic edge-connectivity of strongly regular graphs, Largest 2-regular subgraphs in 3-regular graphs, The contributions of W.T. Tutte to matroid theory, Eigenvalues and perfect matchings, Matchings in graphs. II, On defect-d matchings in graphs, On minimum balanced bipartitions of triangle-free graphs, Graphs with maximal Hosoya index and minimal Merrifield-Simmons index, Integer sets with prescribed pairwise differences being distinct, On packing Hamilton cycles in \(\varepsilon\)-regular graphs, An introduction to matching polynomials, Integer \(k\)-matchings of graphs: \(k\)-Berge-Tutte formula, \(k\)-factor-critical graphs and \(k\)-barriers, On small graphs critical with respect to edge colourings, Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs, Equipartite colorings in graphs and hypergraphs, A note on 1-factors in certain regular multigraphs, Oriented graphs determined by their generalized skew spectrum, Every connected regular graph of even degree is a Schreier coset graph, Relation between the matching number and the second largest distance Laplacian eigenvalue of a graph, Laminar tight cuts in matching covered graphs, A note on 1-factors in graphs, The number of 1-factors in 2k-connected graphs, An extension of Tutte's 1-factor theorem, The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs, An identity for matching and skew-symmetric determinant, Simplified existence theorems for \((g,f)\)-factors, The optimal path-matching problem, A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices, A tight lower bound on the matching number of graphs via Laplacian eigenvalues, Clique minors in graphs and their complements, A note on maximum fractional matchings of graphs, An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem, Multicolour Poisson matching, Fractional matching preclusion number of graphs, Pfaffian structures and critical problems in finite symplectic spaces, PM-compact graphs and vertex-deleted subgraphs, Improved hitting set for orbit of ROABPs, Capacities of graphs and \(2\)-matchings, \(k\)-regular factors and semi-\(k\)-regular factors in graphs, Spanning subgraphs with specified valencies, A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices, On the \(A_\alpha\)-spectral radius of graphs without large matchings, A degree condition for the existence of 1-factors in graphs or their complements, Connected \(k\)-factors in bipartite graphs, Maximum matching in almost linear time on graphs of bounded clique-width, A short proof of Mader's \(\mathcal S\)-paths theorem, Disconnected 2-factors in planar cubic bridgeless graphs, Hadwiger's conjecture for \(K_ 6\)-free graphs, Odd factors of a graph, Extending matchings in graphs: A survey, A class of cubic graphs satisfying Berge conjecture, A \(\vec{P_3}\)-decomposition of tournaments and bipartite digraphs, Monochromatic Cycles in 2-Coloured Graphs, Graph realizations constrained by skeleton graphs, Remarks on regular factors of regular graphs, Maximum matchings in planar graphs via Gaussian elimination, Tutte sets in graphs. II: The complexity of finding maximum Tutte sets, Maximal-\(\Gamma\)-prime Graphen, Unnamed Item, Spanning trails with variations of Chvátal-Erdős conditions, On Two Unsolved Problems Concerning Matching Covered Graphs, Sublinear Estimation of Weighted Matchings in Dynamic Data Streams, Replacing Pfaffians and applications, Packings by Complete Bipartite Graphs, On the Existence of Identifiable Reparametrizations for Linear Compartment Models, Path factors of bipartite graphs, WELL-COVERED GRAPHS: A SURVEY, Narrow sieves for parameterized paths and packings, Covering a cubic graph by 5 perfect matchings, Singular spaces of matrices and their application in combinatorics, Ear-slicing for matchings in hypergraphs, Decomposition theorems for square-free 2-matchings in bipartite graphs, Non-commutative Edmonds' problem and matrix semi-invariants, Unnamed Item, On the complexity landscape of connected \(f\)-factor problems, Edge Proximity Conditions for Extendability in Planar Triangulations, A Simple Criterion for a Graph to have a Perfect Matching, SOME RESULTS ON THE DIFFERENCE OF THE ZAGREB INDICES OF A GRAPH, An algorithmic approach to dual integrality of matching and extensions, Packing of twinned circles on a sphere, The total eccentricity sum of non-adjacent vertex pairs in graphs, Matching for Graphs of Bounded Degree, On two conjectures concerning total domination subdivision number in graphs, Minimum Szeged index among unicyclic graphs with perfect matchings, Almost exact matchings, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Matchings in infinite graphs, On oriented graphs whose skew spectral radii do not exceed 2, KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS, Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two, Chvátal-Erdős conditions and almost spanning trails, Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs, DisjointT-paths in tough graphs, On perfect \(k\)-matchings, Unnamed Item, Unnamed Item, On the anti-Kekulé number and odd cycle transversal of regular graphs, On maximum matchings in cubic graphs with a bounded number of bridge-covering paths, On the existence of 1-factors in partial squares of graphs, Spectral radius and matchings in graphs, Perfect matching and distance spectral radius in graphs and bipartite graphs, Perfect matchings after vertex deletions, The \(A_\alpha\)-spectral radius and perfect matchings of graphs, Processor efficient parallel matching, 2-Matchings and 2-covers of hypergraphs, Forbidden triples for perfect matchings, The computational complexity of the parallel knock-out problem, Maximal matchings in graphs with given minimal and maximal degrees, A factorization theorem for a certain class of graphs, Unnamed Item, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), Spanning subgraphs with specified valencies. (Reprint), Finding maximum square-free 2-matchings in bipartite graphs, On the characteristic polynomials and \(H\)-ranks of the weighted mixed graphs, Polynomial time algorithms for two classes of subgraph problem, Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, Partitioning graphs into induced subgraphs, The complexity of perfect matchings and packings in dense hypergraphs, Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles, Schur and \(e\)-positivity of trees and cut vertices, Über ein graphentheoretisches Ergebnis von T. Gallai, On essentially 4-edge-connected cubic bricks, On the order of certain close to regular graphs without a matching of given size, Projective deformations of weakly orderable hyperbolic Coxeter orbifolds, Matching extendability and connectivity of regular graphs from eigenvalues, The edge-connectivity of strongly 3-walk-regular graphs, Perfect matchings of a graph, Complexity Theory Basics: NP and NL, Graphs and Subgraphs, A note on \(m\)-near-factor-critical graphs, Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs, On the 2-factors of bicubic graphs, 1-Faktoren von Graphen. (1-factors of graphs), On 1-sum flows in undirected graphs, A graph polynomial and its applications, Edmonds polytopes and a hierarchy of combinatorial problems, Optimum matching forests II: General weights, Path problems in skew-symmetric graphs, Disjoint \(A\)-paths in digraphs, Characterizations of graphs \(G\) having all \([1, k\)-factors in \(k G\)], Matchings and skew-symmetric quadratic forms, Fractional matching preclusion for arrangement graphs, Factors of Inserted Graphs, Matching preclusion and conditional matching preclusion problems for the folded Petersen cube, Sharp lower bounds on the fractional matching number, A hypergraph version of the Gallai-Edmonds Theorem, 2-resonant fullerenes, Cores of random graphs are born Hamiltonian, Group connectivity and matchings, Matchings in higher-order Gabriel graphs, \(\vec{P_3}\)-decomposition of directed graphs
