scientific article

From MaRDI portal

Publication:3880849

Jump to:navigation, search

zbMath0439.05001MaRDI QIDQ3880849

László Lovász

Publication date: 1979

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Exact enumeration problems, generating functions (05A15) Hypergraphs (05C65) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Generalized Ramsey theory (05C55) Connectivity (05C40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph theory (05Cxx)

Related Items

The maximum Wiener index of maximal planar graphs, Pattern matching for permutations, Order-preserving indexing, On the complexity of cover-incomparability graphs of posets, A generalization of Sperner's theorem on compressed ideals, Eulerian colorings and the bipartizing matchings conjecture of Fleischner, On constructive characterizations of \((k,l)\)-sparse graphs, On set systems with a threshold property, Graph invertibility and median eigenvalues, Hadwiger's conjecture for circular colorings of edge-weighted graphs, Rounds in combinatorial search, The distribution of the size of the union of cycles for two types of random permutations, Large joints in graphs, A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order, A characterization of graphs without even factors, Improved bounds for Erdős' matching conjecture, General graph pebbling, A linear time algorithm for consecutive permutation pattern matching, Monochromatic loose-cycle partitions in hypergraphs, On super 2-restricted and 3-restricted edge-connected vertex transitive graphs, Two counterexamples on completely independent spanning trees, Nonnegative \(k\)-sums, fractional covers, and probability of small deviations, Super restricted edge connectivity of regular edge-transitive graphs, The maximum genus of vertex-transitive graphs, Fast uniform generation of regular graphs, Mixed discriminants of positive semidefinite matrices, Unavoidable subhypergraphs: \(\mathbf a\)-clusters, Vertex partitions of non-complete graphs into connected monochromatic \(k\)-regular graphs, Isoperimetric inequalities for faces of the cube and the grid, Locally constrained graph homomorphisms -- structure, complexity, and applications, Some order dimension bounds for communication complexity problems, Edge reductions in cyclically \(k\)-connected cubic graphs, Factorizations of regular graphs, Augmenting the edge connectivity of planar straight line graphs to three, On shredders and vertex connectivity augmentation, Kauffman's clock lattice as a graph of perfect matchings: a formula for its height, Average distance in weighted graphs, On the construction of non-2-colorable uniform hypergraphs, Super \(s\)-restricted edge-connectivity of vertex-transitive graphs, Edge-connectivity of regular graphs with two orbits, Connectivity augmentation in planar straight line graphs, Boolean algebras and Lubell functions, Supersaturation and stability for forbidden subposet problems., Growing perfect cubes, Minimizing a monotone concave function with laminar covering constraints, Clique-inserted-graphs and spectral dynamics of clique-inserting, Minimally restricted edge connected graphs, A size-sensitive inequality for cross-intersecting families, Recent results on well-balanced orientations, Bounds on connective constants of regular graphs, Alternating-sign matrices and domino tilings. II, Spectra, Euclidean representations and clusterings of hypergraphs, Which claw-free graphs are perfectly orderable?, Postman tours and cycle covers, List colourings of planar graphs, Graphs with integral spectrum, A comparison of two edge-coloring formulations, Degree-bounded factorizations of bipartite multigraphs and of pseudographs, Minimum congestion spanning trees in planar graphs, Graph connectivity and its augmentation: Applications of MA orderings, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Tensegrity frameworks in one-dimensional space, Color-critical graphs have logarithmic circumference, Eigenvalues and \([1,n\)-odd factors], Subgroups of graph groups, On the complexity of embedding planar graphs to minimize certain distance measures, On a word avoiding near repeats, Graph groups, coherence, and three-manifolds, The polytope of degree sequences, Strong properties in partially ordered sets. I, On the girth of extremal graphs without shortest cycles, A solitaire game played on 2-colored graphs, Cayley sum graphs and eigenvalues of \((3,6)\)-fullerenes, The edge version of Hadwiger's conjecture, Approximation algorithms for maximum latency and partial cycle cover, A deterministic view of random sampling and its use in geometry, Alternating Whitney sums and matchings in trees. II, Applications of antilexicographic order. I: An enumerative theory of trees, Paths and cycles concerning independence edges, Hamilton cycles in circulant digraphs with prescribed number of distinct jumps, Path transferability of graphs with bounded minimum degree, Minimally 3-restricted edge connected graphs, Forbidden pairs for \(k\)-connected Hamiltonian graphs, Clique or hole in claw-free graphs, Ring elements as sums of units., Edges of degree \(k\) in minimally restricted \(k\)-edge connected graphs, On cyclic edge-connectivity of transitive graphs, Domination, independent domination, and duality in strongly chordal graphs, Bounds on graph spectra, On the minimum order of graphs with given semigroup, A new short proof for the Kruskal-Katona theorem, A geometric construction of a superconcentrator of depth 2, Geometrical solution of an intersection problem for two hypergraphs, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, On the succinct representation of graphs, A Chvátal-Erdős condition for (t,t)-factors in digraphs using given arcs, A one-dimensional Whitney trick and Kuratowski's graph planarity criterion, The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families, Some colouring problems for Paley graphs, On learning monotone Boolean functions under the uniform distribution, Elementary bipartite graphs and unique colourability, A new Bollobás-type inequality and applications to \(t\)-intersecting families of sets, On the Erdős-Ko-Rado theorem and the Bollobás theorem for \(t\)-intersecting families, Arrangements of segments that share endpoints: Single face results, Every tree contains a large induced subgraph with all degrees odd, Equitable factorizations of edge-connected graphs, Tough Ramsey graphs without short cycles, Interlacing eigenvalues and graphs, Chromatic invariants for finite graphs: Theme and polynomial variations, One-node cutsets and the dominating set polytope, Tiling pictures of the plane with dominoes, A lattice point problem and additive number theory, A note on linear Sperner families, Defect Sauer results, Partitioning permutations into increasing and decreasing subsequences, Stage-graph representations, Maximum chromatic polynomial of 3-chromatic blocks, A bibliography on chromatic polynomials, The largest transversal numbers of uniform hypergraphs, Path polynomials of a graph, On the average Steiner distance of graphs with presribed properties, On some properties of the series \(\sum_{k=0}^ \infty k^ n x^ k\) and the Stirling numbers of the second kind, On the number of flats spanned by a set of points in \(PG(d,q)\), Choosability of planar graphs, Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM, Zero-sum problems -- a survey, Constructing status injective graphs, All trees contain a large induced subgraph having all degrees 1 (mod \(k\)), Four results about self-blocking clutters, A complementation theorem for perfect matchings of graphs having a cellular completion, Coloring graph products---a survey, The number of clone orderings, Rounding in symmetric matrices and undirected graphs, On the number of group-weighted matchings, On the approximability of some Maximum Spanning Tree Problems, Clustering on trees, A communication problem and directed triple systems, On a problem of Erdős and Moser, Equiangular lines and spherical codes in Euclidean space, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, Strong Tutte type conditions and factors of graphs, Packing cycles in graphs, A new lower bound on the number of edges in colour-critical graphs and hypergraphs, Subgraph trees in graph theory, Chromatic variants of the Erdős--Szekeres theorem on points in convex position., Constructive characterizations for packing and covering with trees, Combined connectivity augmentation and orientation problems, On minimally \(k\)-edge-connected graphs and shortest \(k\)-edge-connected Steiner networks, Generalising some results about right-angled Artin groups to graph products of groups., Problems and results in extremal combinatorics. I., On caterpillar factors in graphs, Enumerating \(k\)-arc-connected orientations, Splitting off edges between two subsets preserving the edge-connectivity of the graph., Wiener index of quadrangulation graphs, Minimum degree conditions for monochromatic cycle partitioning, Analogues of Milner's theorem for families without long chains and of vector spaces, Realizing finite groups in Euclidean space, An upper bound on Wiener indices of maximal planar graphs, Hodge decomposition and the Shapley value of a cooperative game, Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes, A bound on the spectral radius of hypergraphs with \(e\) edges, Borsuk's partition problem and finite point sets, A fast algorithm for cactus representations of minimum cuts, Super restricted edge-connectivity of vertex-transitive graphs, On the structure of minimal winning coalitions in simple voting games, The Steiner \(k\)-Wiener index of graphs with given minimum degree, Research problems from the 19th British Combinatorial Conference, Several families with incomparability and complementarity conditions, Norton algebras of the Hamming graphs via linear characters, On extremal problems concerning the traces of sets, A generalization of the Bollobás set pairs inequality, A Fourier inversion formula for evolutionary trees, On the construction of permutations of a given type kept fixed by conjugation, Group weighted matchings in bipartite graphs, Decomposition of the complete hypergraph into hyperclaws, Mean distance in a tree, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, On multi-coloured lines in a linear space, Bounds on the measurable chromatic number of \({\mathbb{R}}\), Vertex partitions by connected monochromatic \(k\)-regular graphs, Minimal length test vectors for multiple-fault detection, The number of \(k\)-intersections of an intersecting family of \(r\)-sets, Every orientation of a 4-chromatic graph has a non-bipartite acyclic subgraph, On the trace of finite sets, Best possible bounds on the number of distinct differences in intersecting families, Connected graphs of genus g with complementary orbits, Chromatic index of hypergraphs and Shannon's theorem, Analysis of permutation routing algorithms, An analysis of Monte Carlo algorithm for estimating the permanent, Interpolation theorems for domination numbers of a graph, On the dual distance and the gap of a binary code, Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems., A shifting algorithm for continuous tree partitioning, Computers and discovery in algebraic graph theory, Induced subgraphs of a tree with constraint degree, Results and problems on chorded cycles: a survey, Reduced 2-to-1 maps and decompositions of graphs with no 2-to-1 cut sets, A new class of Wilf-equivalent permutations, The generalized Turán number of spanning linear forests, Graph exploration by energy-sharing mobile agents, Merging the A-and Q-spectral theories, Well-mixing vertices and almost expanders, Shadows of 3-Uniform Hypergraphs under a Minimum Degree Condition, Erdős--Szekeres theorem with forbidden order types, A problem of Laczkovich: how dense are set systems with no large independent sets?, Bernoulli trials of fixed parity, random and randomly oriented graphs, Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets, GENERALIZED PASCAL’S PYRAMIDS AND DECISION TREES, Connectivity augmentation in plane straight line graphs, An algorithmic approach to the Lovász local lemma. I, On the connectivity of diamond-free graphs, On a conjecture of Wilf, Some corollaries of a theorem of Whitney on the chromatic polynomial, Dependence polynomials, Cliques and the spectral radius, Random Cayley graphs and expanders, Super cyclically edge-connected vertex-transitive graphs of girth at least 5, Constructing Graphs with No Immersion of Large Complete Graphs, Super-cyclically edge-connected regular graphs, Local Expansion of Symmetrical Graphs, Length lower bounds for reflecting sequences and universal traversal sequences, Matchings in Lattice Graphs and Hamming Graphs, Odd induced subgraphs in graphs with treewidth at most two, Odd induced subgraphs in planar graphs with large girth, On the approximability of some maximum spanning tree problems, A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem, Distance and eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs, Edge Multiplicity and Other Trace Functions, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, New bounds for the chromatic number of graphs, Counting Intersecting and Pairs of Cross-Intersecting Families, Proof of a Packing Conjecture of Bollobás, Partial Shadows of Set Systems, Odd cycles and \(\Theta\)-cycles in hypergraphs, Hypergraph Turán numbers of linear cycles, A Survey on Covering Supermodular Functions, Multiflow Feasibility: An Annotated Tableau, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Edge-Connectivity Augmentations of Graphs and Hypergraphs, Small Union with Large Set of Centers, A Multivariate Faa di Bruno Formula with Applications, Plane graphs with parity constraints, The bell is ringing in speed-scaled multiprocessor scheduling, ON THE DICHROMATIC INDEX OF A DIGRAPH, Lovász, Vectors, Graphs and Codes, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Keeping scores, A counterexample to the bipartizing matching conjecture, On encodings of spanning trees, Joints in graphs, On the Metric $s$--$t$ Path Traveling Salesman Problem, Constructive generation of very hard 3-colorability instances, Optimal shooting: Characterizations and applications, Large spaces of symmetric matrices of bounded rank are decomposable^∗, Forbidding complete hypergraphs as traces, Pattern matching for permutations, Edge-splittings preserving local edge-connectivity of graphs, Weighted cross-intersecting families, On a problem in combinatorial geometry, Restricted permutations, List colourings of planar graphs. (Reprint), Simultaneous well-balanced orientations of graphs, Coloring copoints of a planar point set, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay, On the edge-connectivity of graphs with two orbits of the same size, Domino tilings and Aztec stars, A particular timetable problem: Terminal scheduling, The size-Ramsey number of trees, On a conjecture of Thomassen concerning subgraphs of large girth, Solution to the minimum harmonic index of graphs with given minimum degree, Inequalities for cross-unions of collections of finite sets, Monochromatic cycle partitions of edge-colored graphs, The Typical Structure of Gallai Colorings and Their Extremal Graphs, Hyper-Hamiltonian circulants, Subsets in linear spaces over the finite field \(\mathbb F_3\) uniquely determined by their pairwise sums collection, On the complexity of finding large odd induced subgraphs and odd colorings, Simple groups, fixed point ratios and applications, Graphs Containing TopologicalH, The shifting method and generalized Turán number of matchings, On the Metric $s$--$t$ Path Traveling Salesman Problem, Traces of hypergraphs, An Improvement of Hind's Upper Bound on the Total Chromatic Number, The Erdős-Szekeres Problem, Unnamed Item, Wiener Index and Remoteness in Triangulations and Quadrangulations, Counting copies of a fixed subgraph in \(F\)-free graphs, A quantitative Lovász criterion for Property B, Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees, Degree of indecomposability of certain highly regular zero-one matrices, Strong Chordality of Graphs with Possible Loops, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Kernelization lower bound for permutation pattern matching, A proof of an inequality concerning \(k\)-restricted edge connectivity, The minimum number of minimal codewords in an \([n, k\)-code and in graphic codes], The Erdos-Szekeres problem on points in convex position – a survey, On extremal bipartite graphs with high girth, Construction of Subsets of Finite Positive Hausdorff Measure on the Hyperspace ((X), ρH), On edge connectivity and parity factor, Totally-Balanced and Greedy Matrices, Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs, The Profile Polytope of Nontrivial Intersecting Families, Average distance, minimum degree, and irregularity index, Convergence rate for the number of crossings in a random labelled tree, Complexity of (arc)-connectivity problems involving arc-reversals or deorientations, The saturation spectrum for antichains of subsets, Intersecting families of sets are typically trivial, Four-vertex traces of finite sets, Many Cliques in Bounded-Degree Hypergraphs, Families with restricted matching number and multiply covered shadows, A proof of Frankl's conjecture on cross-union families, Labelled trees and pairs of input-output permutations in priority queues, Learning logic programs with structured background knowledge, Enumeration of hypergraphs, Hamilton-connected Cayley graphs on Hamiltonian groups, Bipartition constrained edge-splitting in directed graphs, Counting domino tilings of rectangles via resultants, Atoms of cyclic edge connectivity in regular graphs, A new contraction technique with applications to congruency-constrained cuts, A note on f-factors in directed and undirected multigraphs, Perfect matchings and perfect squares, Factors of trees, On induced subgraphs with odd degrees, Forbidden subsequences, A problem of Füredi and Seymour on covering intersecting families by pairs, Sufficient conditions for maximally connected dense graphs, Contractible edges in 3-connected graphs, \(K_ 5\) is the only double-critical 5-chromatic graph, Minimizing and maximizing the diameter in orientations of graphs, Some best possible bounds concerning the traces of finite sets, A quick proof of Seymour's theorem on t-joins, General forbidden configuration theorems, \(k\)-cycle resonant graphs, Expanding graphs contain all small trees, König's theorem and bimatroids, Minimum shadows in uniform hypergraphs and a generalization of the Takagi function, Spaces with unique Hausdorff extensions, Permanent and determinant, Partitioning complete bipartite graphs by monochromatic cycles, Line hypergraphs, Splitting property in infinite posets, NP-hard problems in hierarchical-tree clustering, Decompositions of hypergraphs into hyperstars, Extremal 3-connected graphs, On the nonuniform Fisher inequality, A lower bound for read-once-only branching programs, On matroids induced by packing subgraphs, Exact solution of some Turán-type problems, On hypergraph acyclicity and graph chordality, Construction of infinite de Bruijn arrays, On two extremal matrix problems, The longest cycles in a graph G with minimum degree at least \(| G| /k\), Random packing by \(\rho\)-connected \(\rho\)-regular graphs, More odd graph theory, On automorphisms of line-graphs, A remark concerning arithmetic progressions, On minimal graphs, The bias of three pseudo-random shuffles, The 2-homeotoxal tilings of the plane and the 2-sphere, On numbers related to partitions of unlike objects and occupancy problems, Upper bound on the order of tau-critical hypergraphs, Hamiltonian paths in vertex-symmetric graphs of order 5p, Path-positive graphs, The partition polynomial of a finite set system, Trees with 1-factors and oriented trees, Vertex coverings by monochromatic cycles and trees, A sharpening of Fisher's inequality, Graphs with given automorphism group and few edge orbits, Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems, Arrow relations on families of finite sets, Multicolored forests in bipartite decompositions of graphs, A matching algorithm for regular bipartite graphs, A short proof that matching matroids are transversal, A volume associated with \(m{\times}n\) matrices, \(L_ 1\) shortest paths among polygonal obstacles in the plane, On a theorem of Mader, Cycles containing many vertices of large degree, Forwarding indices of \(k\)-connected graphs, Lower bounds on the length of universal traversal sequences, Alternating-sign matrices and domino tilings. I, On obstructions to small face covers in planar graphs, Helly property in finite set systems, Factors in graphs with odd-cycle property, Formal power series of logarithmic type, On the approximation of protein threading, Labelled trees and pairs of input--output permutations in priority queues, Packing and covering k-chain free subsets in Boolean lattices, Counting points on varieties over finite fields related to a conjecture of Kontsevich, Hamiltonian paths in Cayley graphs, 6-regular Cayley graphs on abelian groups of odd order are Hamiltonian decomposable, Non-separating trees in connected graphs, A class of hypergraphs satisfying an inequality of Lovasz, Characterizations of strongly chordal graphs, Eigenvalue interlacing and weight parameters of graphs, A class of `matching-equivalent' bipartite graphs, A note on the probabilistic approach to Turan's problem, Long cycles generate the cycle space of a graph, Orientations with single source and sink, Signed domination in regular graphs and set-systems, Forests, colorings and acyclic orientations of the square lattice, Removing randomness in parallel computation without a processor penalty, Effect of connectivity in an associative memory model, Classes of chromatically unique or equivalent graphs, Hypergraphs without a large star, Reconstruction from vertex-switching, Forbidding just one intersection, On factors with all degrees odd, Factoring distance matrix polynomials, A generalization of Dirac's theorem, Path positivity and infinite Coxeter groups, A characterization of totally balanced hypergraphs, On the average rank of an element in a filter of the partition lattice, On 1-factorizability of Cayley graphs, Packings by cliques and by finite families of graphs, The average order of a matrix, On induced subgraphs of trees, with restricted degrees, Any four independent edges of a 4-connected graph are contained in a circuit, Polytopes determined by hypergraph classes, On determination of graph G whose bond lattice \({\mathcal L}(G)\) is modular

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3880849&oldid=17511430"