Publication:3852212
From MaRDI portal
zbMath0419.05031MaRDI QIDQ3852212
Publication date: 1978
complexity; matching; cycles; extremal graphs; diameter; packing; connectivity; extremal problems; colourings; complete subgraphs; extremal graph theory; Turan; topological subgraphs
05C35: Extremal problems in graph theory
05-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
Related Items
Approximating \(k\)-spanner problems for \(k>2\), The binding number of a graph and its pancyclism, Optimal parallel algorithms on planar graphs, On some extremal connectivity results for graphs and matroids, Pancyclic properties of the graph of some 0-1 polyhedra, Regular subgraphs of almost regular graphs, Topological cliques of random graphs, The total chromatic number of graphs having large maximum degree, Excluding induced subgraphs. II: Extremal graphs, On the calculation of transitive reduction-closure of orders, Bounded vertex colorings of graphs, Query strategies for priced information, A common extension of the Erdős-Stone theorem and the Alon-Yuster theorem for unbounded graphs, On the complexity of fixed parameter clique and dominating set, Vertex-disjoint quadrilaterals in graphs, Girth and treewidth, More on the power of chain rules in context-free grammars, The structure of social decision functions, Recent trends in combinatorial optimization, Combinatorial dimension and random sets, Lower bounds for the clique and the chromatic numbers of a graph, An edge extremal result for subcohesion, Graph decompositions without isolates, Girth in graphs, A generalization of the Bondy-Chvátal theorem on the k-closure, Embedding of \(\ell^ k_{\infty}\) in finite dimensional Banach spaces, Geometrical solution of an intersection problem for two hypergraphs, The behaviour of (n over \(k,\dots ,k,n-ik)c^ i/i!\) is asymptotically normal, How to make a graph bipartite, Extremal problems whose solutions are the blowups of the small Witt- designs, New lower bound techniques for distributed leader finding and other problems on rings of processors, The structure of the models of decidable monadic theories of graphs, Decomposing oriented graphs into transitive tournaments, On the diameter of separated point sets with many nearly equal distances, Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree, An improved bound for the monochromatic cycle partition number, Packing directed cycles efficiently, Spectral radii of graphs with given chromatic number, Graph factors and factorization: 1985--2003: a survey, Cubic maximal nontraceable graphs, Packing of two digraphs into a transitive tournament, Eigenvalues and forbidden subgraphs. I., New exact values of the maximum size of graphs free of topological complete subgraphs, Minimum degree and the minimum size of \(K_2^t\)-saturated graphs, Optimal fault-tolerant routings with small routing tables for \(k\)-connected graphs, Graphs without minor complete subgraphs, A data structure useful for finding Hamiltonian cycles, Implicit-degrees and circumferences, Unique graph homomorphisms onto odd cycles. II, Edge reductions in cyclically \(k\)-connected cubic graphs, Ordered colourings of graphs, On the maximum density of graphs which have no subcontraction to \(K^ r\)., A note on the probabilistic approach to Turan's problem, Minimally k-connected graphs of low order and maximal size, On color critical graphs, Further nonparametric tests for comparing dissimilarity matrices based on the relative neighborhood graph, An extremal problem for sets with applications to graph theory, Every poset has a central element, Factors of regular graphs, Separating pairs of points of standard boxes, Time-space trade-offs for branching programs, The complexity of colouring problems on dense graphs, Minimally 3-connected graphs, The average size of an independent set in graphs with a given chromatic number, Maximum induced trees in graphs, Sufficient conditions for maximally connected dense graphs, Counterexample to a conjecture on Hamilton cycles, On lattices with Möbius function \(\pm 1,0\), Extremal problems concerning transformations of the set of edges of the complete graph, Two theorems on packings of graphs, Edge-connectivity augmentation problems, Inequalities relating degrees of adjacent vertices to the average degree, What can we hope to accomplish in generalized Ramsey theory ?, Another extremal problem for Turan graphs, Local \(k\)-colorings of graphs and hypergraphs, The binding number of a graph and its triangle, The connectivities of adjacent tree graphs, A lower bound on connectivities of matroid base graphs, On common edges in optimal solutions to traveling salesman and other optimization problems, Intersection properties of boxes. I: An upper-bound theorem, The number of triangles in a \(K_ 4\)-free graph, Exact solution of some Turán-type problems, Simplicial decompositions of graphs: A survey of applications, Triad count statistics, Efficient approximate solution of sparse linear systems, The Erdős-Jacobson-Lehel conjecture on potentially \(P_k\)-graphic sequence is true, Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases, On graphs with equal edge connectivity and minimum degree, The distribution of the maximum degree of a random graph, Girth, valency, and excess, Ramsey numbers for matchings, Degree sequences of random graphs, Hadwiger's conjecture is true for almost every graph, Sorting in one round, The size of connected hypergraphs with prescribed covering number, Critically partitionable graphs. II, Equitable and proportional coloring of trees, On finite Ramsey numbers, The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices, Sur les graphes admettant le nombre maximum de sous-graphes à trois sommets et deux arêtes, et les paires d'ordres totaux qui maximisent \(| Rho\)- Tau\(|\). (On the graphs which admit the maximal number of subgraphs on three vertices and with two edges and the totally ordered pairs which maximize \(| Rho\)- Tau\(|)\), The number of complete subgraphs of equi-partite graphs, An extremal problem concerning graphs not containing \(K_t\) and \(K_{t,n-t}\), Vertex-disjoint hexagons with chords in a bipartite graph, Triangles in claw-free graphs, Toughness and the existence of \(k\)-factors. III, Sign-balanced covering matrices, Graph partitions with minimum degree constraints, Choosability of \(K_5\)-minor-free graphs, Every \(H\)-decomposition of \(K_n\) has a nearly resolvable alternative, Subdivisions of transitive tournaments, Local majorities, coalitions and monopolies in graphs: A review, Wavelength routing in optical networks of diameter two, On self-complementary supergraphs of (\(n,n\))-graphs, Sparse graph certificates for mixed connectivity, The number of distinct subset sums of a finite set of vectors, Orthogonal decomposition and packing of complete graphs, Another extremal property of some Turán graphs, An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees, An upper bound on the Ramsey number of trees, Packing of graphs - a survey, The number of graphs without forbidden subgraphs, Quadrangulations and 4-color-critical graphs, A new Turán-type theorem for cliques in graphs, Superfluous edges and exponential expansions of de Bruijn and Kautz graphs, Lower bounds on the independence number in terms of the degrees, Some remarks on packing trees, Regular \(K_n\)-free graphs, On generalized Ramsey theory: The bipartite case, Some results related to the evasiveness conjecture., The extremal function for complete minors, Fragmentability of graphs, Covering non-uniform hypergraphs, Odd wheels in graphs, Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem, Almost-spanning subgraphs with bounded degree in dense graphs, Directed virtual path layouts in ATM networks, Disjointly representing set systems, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., On finding common neighborhoods in massive graphs., Stability theorems for cancellative hypergraphs, Geometric graphs with no self-intersecting path of length three, A variation of a classical Turán-type extremal problem, The number of edge-disjoint transitive triples in a tournament, Broadcast time and connectivity, On-line generalized Steiner problem, On the strength of comparisons in property testing, On the maximum density of 0-1 matrices with no forbidden rectangles, Tough Ramsey graphs without short cycles, Explicit construction of graphs with an arbitrary large girth and of large size, Greedy clique decompositions and the Turán numbers, The isomorphic factorization of complete tripartite graphs \(K(m,n,s)\).--- A proof of F. Harary, R.W. Robinson and N.C. Wormald's conjectureure, On independent cycles and edges in graphs, On the distortion required for embedding finite metric spaces into normed spaces, Cycle-saturated graphs of minimum size, Large \(2P_ 3\)-free graphs with bounded degree, Extremal functions for sequences, Packing three trees, 2-factors in dense graphs, Zero-sum problems -- a survey, The number of complements of a topology on \(n\) points is at least \(2^ n\) (except for some special cases), A characterization of the components of the graphs \(D(k,q)\), Matrix rigidity, Intersecting designs, Matroidal bijections between graphs, Posets with maximal Möbius function, Mutually complementary partial orders, Construction of a family of graphs with a small induced proper subgraph with minimum degree 3, The smallest number of edges in a 2-connected graph with specified diameter, Odd cycles and \(\Theta\)-cycles in hypergraphs, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, Cycles and stability, Packing \(d\)-degenerate graphs, A spectral condition for odd cycles in graphs, On bags and bugs, Characterizing minimally \(n\)-extendable bipartite graphs, Shifted products that are coprime pure powers, Nearly equal distances and Szemerédi's regularity lemma, A survey on labeling graphs with a condition at distance two, Set colourings of graphs. (Reprint), Asymptotically optimal \(K_k\)-packings of dense graphs via fractional \(K_k\)-decompositions, Strong Rabin numbers of folded hypercubes, On a Turán-type hypergraph problem of Brown, Erdős and T. Sós, The recognizability of sets of graphs is a robust property, Large planar subgraphs in dense graphs, Asymptotically large (\(\Delta,D\))-graphs, A hierarchy of randomness for graphs, On graph problems in a semi-streaming model, Extremal connectivity for topological cliques in bipartite graphs, Unnamed Item, Unnamed Item, Some corollaries of a theorem of Whitney on the chromatic polynomial, Dependence polynomials, New results on the Zarankiewicz problem, A New Similarity Measure and Its Use in Determining the Number of Clusters in a Multivariate Data Set, Dense graphs are antimagic, A unified framework for off-line permutation routing in parallel networks, Regular graphs whose subgraphs tend to be acyclic, Shortest‐path metric approximation for random subgraphs, Pentagons and cycle coverings, Improved lower bounds on the randomized complexity of graph properties, Biased graphs. II: The three matroids, Constructing the relative neighborhood graph in 3-dimensional Euclidean space, Lower bounds on the stability number of graphs computed in terms of degrees, Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s, The chromatic uniqueness of complete bipartite graphs, Long cycles in subgraphs with prescribed minimum degree, Saturated \(r\)-uniform hypergraphs, On some factor theorems of graphs, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Generalized local colorings of graphs, Counting and cutting cycles of lines and rods in space, Davenport-Schinzel theory of matrices, Bounds on the number of complete subgraphs, On sparse spanners of weighted graphs, On small graphs with highly imperfect powers, Matching theory -- a sampler: From Dénes König to the present, Turán theorems with repeated degrees, Graphs with small diameter after edge deletion, Examples of products giving large graphs with given degree and diameter, Reducible chains in several types of 2-connected graphs, On games of incomplete information, Asymptotic growth of sparse saturated structures is locally determined, Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties, A Turán-type theorem on chords of a convex polygon, On embedding of graphs into Euclidean spaces of small dimension, Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs, Uniquely colorable graphs, Chromatic number, girth and maximal degree, Dense neighbourhoods and Turan's theorem, Set colourings of graphs, Helly families of maximal size, Radius, diameter, and minimum degree, Covering graphs: The covering problem solved, On the Ramsey problem for multicolor bipartite graphs, A two-person game on graphs where each player tries to encircle his opponent's men, Cycle factors in dense graphs, Polarities and \(2k\)-cycle-free graphs, Monadic second-order logic, graph coverings and unfoldings of transition systems, Two path extremal graphs and an application to a Ramsey-type problem, The smallest Ramsey numbers, Another cycle structure theorem for Hamiltonian graphs, Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling, Defining sets and uniqueness in graph colorings: A survey, Induced subgraphs of given sizes, Edge-disjoint spanners of complete graphs and complete digraphs, On quadrilaterals in a graph, Optimal factorizations of families of trees, On the maximum number of independent cycles in a graph, Norm-graphs: Variations and applications, Mutual placement of bipartite graphs, Superconcentrators of depths 2 and 3; odd levels help (rarely), Minors of quasi 4-connected graphs, Intersecting designs from linear programming and graphs of diameter two, Subdivision thresholds for two classes of graphs, On induced subgraphs of trees, with restricted degrees, Acyclic edge-colorings of sparse graphs, Embedding graphs of small size, Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, On the contractibility of a digraph onto \(K_ 4^*\), A \(k\)-structure generalization of the theory of 2-structures, On induced subgraphs with odd degrees, Independent cycles with limited size in a graph, The decision-tree complexity of element distinctness, \(k\)-connectivity and decomposition of graphs into forests, Problems and results in discrete mathematics, On a matrix partition conjecture, Fractional v. integral covers in hypergraphs of bounded edge size, The structure of quasi 4-connected graphs, The colour theorems of Brooks and Gallai extended, A note on packing of three forests, Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture, Dirac's conjecture on \(K_ 5\)-subdivisions, Stage-graph representations, The VC-dimension of set systems defined by graphs, Uniquely total colorable graphs, Tournaments as strong subcontractions, Independent transversals in \(r\)-partite graphs, Combinatorial aspects of geometric graphs, Planar stage graphs: Characterizations and applications, Handsome proof-nets: Perfect matchings and cographs, 2-connected graphs with small 2-connected dominating sets., The size of bipartite graphs with a given girth, Topological minors in graphs of large girth, Packing closed trails into dense graphs., Ramsey numbers involving large dense graphs and bipartite Turán numbers, Graphs with large maximum degree containing no odd cycles of a given length, On completely positive graphs and their complements, Covering vertices of a graph by \(k\) disjoint cycles, The smallest degree sum that yields potentially \(_{k}C_{\ell}\)-graphic sequences, On the monotonicity of games generated by symmetric submodular functions., Hereditary systems and greedy-type algorithms., Problems and results in extremal combinatorics. I., Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences, Packing of graphs and permutations -- a survey, Vertex-symmetric generalized Moore graphs., A note on the ``packing of two copies of some trees into their third power, Packing and decomposition of graphs with trees, Circuit decompositions of Eulerian graphs, Linear coloring of graphs, Sufficient conditions for equality of connectivity and minimum degree of a graph, Unnamed Item, Unnamed Item, The Hamilton circuit problem on grids, The lattice of integral flows and the lattice of integral cuts on a finite graph, Unnamed Item, Edge-superconnectivity of cages, A note on a conjecture about cycles with many incident chords, Unnamed Item, Unnamed Item, Integer and fractional packing of families of graphs, Testing graphs for colorability properties*, Acyclic graph coloring and the complexity of the star chromatic number, N‐extendability of symmetric graphs, Extremal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msub></mml:math>-free bipartite graphs, Maximal antiramsey graphs and the strong chromatic number, Large deviations for sums of partly dependent random variables, The decomposition threshold for bipartite graphs with minimum degree one, Unnamed Item, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Embedding with a Lipschitz function, On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph, Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs, David and Goliath Commitments: UC Computation for Asymmetric Parties Using Tamper-Proof Hardware, Rupture degree of graphs, On an anti‐Ramsey problem of Burr, Erdős, Graham, and T. Sós, Extremal non-bipartite regular graphs of girth 4, Minimum vertex‐diameter‐2‐critical graphs, Paul Erdős, 1913-1996, On the elusiveness of Hamiltonian property, Contributions to the problem of Zrankiewicz, The penultimate rate of growth for graph properties, A connection between coding theory and polarized partition relations, Independent triangles covering given vertices of a graph, The communication complexity of enumeration, elimination, and selection, Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles), On partitions of a rectangle into rectangles with restricted number of cross sections, Some results on placing bipartite graphs of maximum degree two, Hamiltonian Chains in Hypergraphs, On extremal bipartite graphs with high girth, Tripartite Ramsey numbers for paths, Unnamed Item, Factors and factorizations of graphs—a survey, Graphs and degree sequences. I, A reduction method to find spanning Eulerian subgraphs, Graphs with unavoidable subgraphs with large degrees, Lower bounds on the number of triangles in a graph, Graph spanners, Graphs without four-cycles, Do 3n − 5 edges force a subdivision ofK5?, Upper bounds for harmonious colorings, Coloring Clique-free Graphs in Linear Expected Time, Some upper bounds on the total and list chromatic numbers of multigraphs, Message-optimal protocols for Byzantine Agreement, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Extremal problems in graph theory, Generalized Rotation numbers, New upper bounds for the greatest number of proper colorings of a (V,E)‐graph
