scientific article; zbMATH DE number 1432797

Publication date: 17 April 2000

Full work available at URL: http://www.emis.de/monographs/Diestel/en/

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graph theory (05Cxx)

Related Items

Centrality measures for node-weighted networks via line graphs and the matrix exponential, The deficiency of all generalized Hertz graphs and minimal consecutively non-colourable graphs in this class, Maximum weighted induced subgraphs, A structure theory for graphs with fixed smallest eigenvalue, Cycle covers. II: Circuit chain, Petersen chain and Hamilton weights., Excluded-minor characterization of apex-outerplanar graphs, External-memory depth-first search algorithm for solid grid graphs, Separation dimension of graphs and hypergraphs, Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs, Complexity issues in color-preserving graph embeddings, Dense trees: a new look at degenerate graphs, Distributed adaptive neural control of nonlinear multi-agent systems with unknown control directions, A survey on modeling of microgrids -- From fundamental physics to phasors and voltage sources, Planar groups, Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs, Cops and robbers from a distance, Forbidden subgraphs and the existence of spanning \(k\)-trees, On Ramsey (\(K_{1,m},\mathcal{G}\))-minimal graphs, Combinatorial characterizations of the Cohen-Macaulayness of the second power of edge ideals, The contraction principle for set valued mappings on a metric space with a graph, On a conjecture on the balanced decomposition number, Critical sets for Sudoku and general graph colorings, Maximum induced forests in graphs of bounded treewidth, Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Graph factors modulo \(k\), Note on the subgraph component polynomial, Boxicity of line graphs, Forbidden induced subgraphs for star-free graphs, Some fixed point results on a metric space with a graph, Effective feature construction by maximum common subgraph sampling, A semigroup proof of the bounded degree case of S.B. Rao's conjecture on degree sequences and a bipartite analogue, A new framework of consensus protocol design for complex multi-agent systems, Computing inertia sets using atoms, Random 2 XORSAT phase transition, Some inequalities for the Tutte polynomial, The minimum semidefinite rank of the complement of partial \(k\)-trees, On the Colin de Verdière number of graphs, The competition number of a graph and the dimension of its hole space, Tension continuous maps -- their structure and applications, A branch-and-price approach for harvest scheduling subject to maximum area restrictions, Drawn \(k\)-in-a-row games, A characterization of partial blocks in weighted graphs, Lower bounds on kernelization, The large deviation principle for the Erdős-Rényi random graph, On the maximum number of cliques in a graph embedded in a surface, When the unit, unitary and total graphs are ring graphs and outerplanar, Entire colouring of plane graphs, Security concepts for the dynamics of autonomous vehicle networks, Spanning closed walks and TSP in 3-connected planar graphs, A generalization of Menger's theorem, Cut ideals of \(K_{4}\)-minor free graphs are generated by quadrics, On large semi-linked graphs, A note on vertex colorings of plane graphs, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Edge-signed graphs with smallest eigenvalue greater than \(-2\), 2-factors and independent sets on claw-free graphs, On partitioning the edge set of a graph into internally disjoint paths without exterior vertices, Polynomial treewidth forces a large grid-like-minor, Communication in repeated network games with imperfect monitoring, The \(a\) and \((a, b)\)-analogs of Zagreb indices and coindices of graphs, Neighborhood equivalence for multibranched surfaces in 3-manifolds, Generating and counting unlabeled \(k\)-path graphs, Spanning \(k\)-forests with large components in \(K_{1,k+1}\)-free graphs, Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\), Independent sets in graphs, Network characterizations for excluding Braess's paradox, On first-order definitions of subgraph isomorphism properties, An advance in infinite graph models for the analysis of transportation networks, Cops and robbers ordinals of cop-win trees, A parametric description of cities for the normative analysis of transport systems, Consensus in networks with arbitrary time invariant linear agents, Synthesis of deterministic top-down tree transducers from automatic tree relations, On graphs uniquely defined by their \(K\)-circular matroids, Forbidden structures for planar perfect consecutively colourable graphs, Line-distortion, bandwidth and path-length of a graph, \(k\)-circular matroids of graphs, A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces, On graph equivalences preserved under extensions, Min-max tree covers of graphs., Logical aspects of Cayley-graphs: the group case, Girth and treewidth, The Erdős-Menger conjecture for source/sink sets with disjoint closures, On the Ramsey numbers for stars versus complete graphs, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals, On monochromatic arm exponents for 2D critical percolation, Two cooperative versions of the guessing secrets problem, Group flow, complex flow, unit vector flow, and the \((2 + \epsilon)\)-flow conjecture, Distance-restricted matching extension in triangulations of the torus and the Klein bottle, On the treewidth of dynamic graphs, When the line graphs of the unit, unitary and total graphs are planar and outerplanar, A linear-time algorithm for the longest path problem in rectangular grid graphs, Cyclic matrices of weighted digraphs, Parameterized algorithm for eternal vertex cover, Multi-objective robust cross-market mixed portfolio optimization under hierarchical risk integration, A note on packing two copies of a tree into a graph with small maximum degree, An approach to the performance of SPC product codes on the erasure channel, Counting the number of non-equivalent vertex colorings of a graph, Fano colourings of cubic graphs and the Fulkerson conjecture, Using interval arithmetic to prove that a set is path-connected, Algebraic Combinatorics on Trace Monoids: Extending Number Theory to Walks on Graphs, Some classes of perfect annihilator-ideal graphs associated with commutative rings, Perfect Nilpotent Graphs, Well-mixing vertices and almost expanders, Equitable d-degenerate Choosability of Graphs, Survey on Regularity of Symbolic Powers of an Edge Ideal, Independent Sets in Restricted Line of Sight Networks, Extremal Khovanov homology and the girth of a knot, Girth, minimum degree, independence, and broadcast independence, Unnamed Item, Sum-list-colouring of θ-hypergraphs, Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts, On the lossy kernelization for connected treedepth deletion set, Trees with a unique maximum independent set and their linear properties, The first three largest values of the spectral norm of oriented bicyclic graphs, Matrix functions in network analysis, Sparsity of weighted networks: measures and applications, Some design considerations for cluster randomized trials with binary responses, An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem, Combinatorial inversion in edge-weighted unicyclic graphs, Circular flow number of Goldberg snarks, Highly Connected Subgraphs with Large Chromatic Number, Signed graphs with maximum nullity two, Unnamed Item, On 2-cycles of graphs, Unit read-once refutations for systems of difference constraints, Asymmetry cannot solve the circularity/regress problem of property structuralism, Synchronization in directed nonlinear complex networks under intermittent stochastic control, On transit functions in weighted graphs, Unnamed Item, Regularity and projective dimension of some class of well-covered graphs, Patterns in Khovanov link and chromatic graph homology, Planarity and outerplanarity indexes of the unit, unitary and total graphs, Chromatic index, treewidth and maximum degree, Some properties of comaximal ideal graph of a commutative ring, Acyclic sum-list-colouring of grids and other classes of graphs, On the characteristic polynomial of the power of a path., Testing subgraphs in directed graphs, Cayley factorization and the area principle, Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits, Unnamed Item, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, Directed Path-Decompositions, The descriptive complexity of subgraph isomorphism without numerics, Informational Braess’ Paradox: The Effect of Information on Traffic Congestion, Implosive graphs: Square-free monomials on symbolic Rees algebras, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, When a total graph associated with a commutative ring is perfect?, Algorithmic Applications of Tree-Cut Width, Markov bases and toric ideals for some contingency tables, Improved Bounds for the Excluded-Minor Approximation of Treedepth, Drazin inverse of singular adjacency matrices of directed weighted cycles, Communication Complexity of Pairs of Graph Families with Applications, New Clusterization Method Based on Graph Connectivity Search, On the Vanishing of Discrete Singular Cubical Homology for Graphs, Cycle decompositions and constructive characterizations, On the Limiting Behavior of Parameter-Dependent Network Centrality Measures, Colorings of the Graph K ᵐ 2 + Kn, Unnamed Item, Unnamed Item, Unnamed Item, Pattern Formation by Oblivious Asynchronous Mobile Robots, 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs, A Fast Algorithm for Knapsack Problem with Conflict Graph, On the Aα spectrum of the zero-divisor graphs, On degree sequences of undirected, directed, and bidirected graphs, Planarity and outerplanarity indexes of the zero-divisor graphs, A degree bound on decomposable trees, Tree-decompositions with bags of small diameter, An integrality theorem of root systems, Enumerating non-crossing minimally rigid frameworks, A rainbow Ramsey analogue of Rado's theorem, An extension of Hall's theorem for partitioned bipartite graphs, How to use spanning trees to navigate in graphs, Counting maximal antichains and independent sets, Synchronization of chaotic neural networks with delay in irregular networks, A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs, A note on the Hadwiger number of circular arc graphs, The inertia set of a signed graph, Spanners for bounded tree-length graphs, Local topological toughness and local factors, Boxicity and treewidth, On the reconstruction of planar graphs, Every planar graph is 1-defective \((9,2)\)-paintable, A linear kernel for finding square roots of almost planar graphs, Genera and minors of multibranched surfaces, Fan-crossing free graphs and their relationship to other beyond-planar graphs, Towards a polynomial kernel for directed feedback vertex set, Robustness of distributed averaging control in power systems: time delays \& dynamic communication topology, Fixed-parameter tractable distances to sparse graph classes, Edge fault-tolerance of strongly Menger edge connected graphs, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, On compiling structured CNFs to OBDDs, Odd induced subgraphs in graphs with treewidth at most two, Meta-kernelization using well-structured modulators, Comparison between regularity of small symbolic powers and ordinary powers of an edge ideal, On the Generation of Curvilinear Meshes Through Subdivision of Isoparametric Elements, Spectral norm of oriented graphs, Discrete cubical and path homologies of graphs, Permutation monoids and MB-homogeneity for graphs and relational structures, Winding indexes of Max. and Min. Hamiltonians in N-Gons, The connected vertex cover problem in \(k\)-regular graphs, Line-graphs of cubic graphs are normal, Edge degrees and dominating cycles, On tension-continuous mappings, Graph kernels and Gaussian processes for relational reinforcement learning, Classes of perfect graphs, The smooth structure of the moduli space of a weighted series-parallel graph, The inverse inertia problem for the complements of partial \(k\)-trees, Domatic partitions of computable graphs, Belief consistency and trade consistency, Flow-continuous mappings -- the influence of the group, Prescribed edges and forbidden edges for a cycle in a planar graph, On a base exchange game on bispanning graphs, Universal construction mechanism for networks from one-dimensional symbol sequences, Graphs associated with matrices over finite fields and their endomorphisms, Bounded-width QBF is PSPACE-complete, Topological Index Analysis Applied to Coupled Flow Networks, Even subgraphs of bridgeless graphs and 2-factors of line graphs, On the number of components in 2-factors of claw-free graphs, Renormalization flow for unrooted forests on a triangular lattice, Algebraic characterizations of outerplanar and planar graphs, The structure of \(K_{3,3}\)-subdivision-free toroidal graphs, Relative length of longest paths and longest cycles in triangle-free graphs, Engel graph associated with a group., Graphs (networks) with golden spectral ratio, Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension, Chromatic capacity and graph operations, Subclasses of \(k\)-trees: characterization and recognition, Non-zero disjoint cycles in highly connected group labelled graphs, Graphs and obstructions in four dimensions., Pushing squares around, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Irreducible snarks of given order and cyclic connectivity, On cycles through specified vertices, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, A class of trees and its Wiener index, How to recycle your facets, The carvingwidth of hypercubes, Homometric sets in trees, Spatially-distributed coverage optimization and control with limited-range interactions, Nowhere-zero 3-flows in abelian Cayley graphs, Reconstructing the number of blocks of an infinite graph, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Ore-type degree condition for heavy paths in weighted graphs, On the S-Labeling problem, Packing of (0, 1)-matrices, Mathematical programming models for some smallest-world problems, Monotone maps, sphericity and bounded second eigenvalue, High connectivity keeping sets in graphs and digraphs, A refined search tree technique for dominating set on planar graphs, On the maximum number of cycles in a Hamiltonian graph, Constructions of families of three-dimensional polytopes, characteristic patches of fullerenes, and Pogorelov polytopes, Continuous graph partitioning for camera network surveillance, Forcing large transitive subtournaments, Complete forcing numbers of catacondensed hexagonal systems, Eigenvalue conditions for induced subgraphs, Triangle-factors in powers of graphs, Unions of perfect matchings in cubic graphs, Zero-divisor graphs for semigroups of order 7., Non-intersecting perfect matchings in cubic graphs (Extended abstract), Equivalence of Jackson's and Thomassen's conjectures, Cooperative interval games: mountain situations with interval data, On quantum symmetries of compact metric spaces, Dual power assignment optimization and fault tolerance in WSNs, Obstructions to a small hyperbolicity in Helly graphs, Computation of contour integrals on \( \mathcal{M}_{0,n} \), \(\Lambda\) scattering equations, Stanley-Reisner rings with large multiplicities are Cohen-Macaulay, A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, The circular chromatic index of graphs of high girth, Heavy fans, cycles and paths in weighted graphs of large connectivity, Network topology and the efficiency of equilibrium, Short cycle connectivity, Mobility of vertex-transitive graphs, On the Hadwiger's conjecture for graph products, On a cycle through a specified linear forest of a graph, On short paths through prescribed vertices of a graph, Classes of cycle bases, New exact values of the maximum size of graphs free of topological complete subgraphs, On the number of matchings of a tree, A constructive characterization of 3-connected triangle-free graphs, The Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs, Vertex-oblique graphs, Achievable sets, brambles, and sparse treewidth obstructions, On the number of spanning trees in graphs with multiple edges, There exist highly critically connected graphs of diameter three, A relaxed Hadwiger's conjecture for list colorings, A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\), Structured proportional representation, Null decomposition of trees, Bipartite minors, Signed graphs whose signed Colin de Verdière parameter is two, Meta-kernelization with structural parameters, CHY loop integrands from holomorphic forms, On immersions of uncountable graphs, Size-treewidth tradeoffs for circuits computing the element distinctness function, On the structure and deficiency of \(k\)-trees with bounded degree, Absolute algebraic connectivity of double brooms and trees, Graphs whose positive semi-definite matrices have nullity at most two, Solving problems on graphs of high rank-width, On the core-nilpotent decomposition of trees, Maximum likelihood threshold and generic completion rank of graphs, A multiestimation-based scheme for modelling single-input-single-output discrete adaptive control systems, Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs, Three-connected graphs whose maximum nullity is at most three, Graph powers and \(k\)-ordered hamiltonicity, Friendship decompositions of graphs, On planar and non-planar graphs having no chromatic zeros in the interval(1,2), Another proof of the 5-choosability of \(K_5\)-minor-free graphs, Optimal selection of essential interconnections for structural controllability in heterogeneous subsystems, Facet defining inequalities among graph invariants: The system graphedron, Characterizing and recognizing 4-map graphs, On embeddability and stresses of graphs, Min-max cover of a graph with a small number of parts, Topological graph description of multicellular dynamics based on vertex model, On the parameterized complexity of layered graph drawing, Ring graphs and complete intersection toric ideals, On dual power assignment optimization for biconnectivity, Tree-width of graphs without a \(3\times 3\) grid minor, Parameterized graph cleaning problems, Augmented nodal matrices and normal trees, Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs, Irreducible triangulations are small, About acyclic edge colourings of planar graphs, Perfect matchings with restricted intersection in cubic graphs, Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, Efficient approximation algorithms for shortest cycles in undirected graphs, Computing sharp 2-factors in claw-free graphs, A one-round secure message broadcasting protocol through a key sharing tree, Roughness in Cayley graphs, Multiscale stochastic modeling for tractable inference and data assimilation, A note on \(k\)-walks in bridgeless graphs, On compact and efficient routing in certain graph classes, Forbidden subgraphs and the existence of paths and cycles passing through specified vertices, Generating 3-vertex connected spanning subgraphs, Path-comprehensive and vertex-pancyclic properties of super line graph \(\mathcal L_2(G)\), Acyclic edge coloring of subcubic graphs, Non-separating 2-factors of an even-regular graph, Nodal domains and spectral minimal partitions, On \(k\)-connectivity problems with sharpened triangle inequality, A clique-difference encoding scheme for labelled \(k\)-path graphs, Spectral structure of the Laplacian on a covering graph, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, A polynomial-time algorithm to find a linkless embedding of a graph, A complex network approach to text summarization, The equitable dispersion problem, Bounds on isoperimetric values of trees, On the OBDD size for graphs of bounded tree- and clique-width, Hadwiger number and the Cartesian product of graphs, Minimum entropy coloring, Covering graphs with few complete bipartite subgraphs, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Hadwiger's conjecture for proper circular arc graphs, On tree-partition-width, Critically loaded queueing models that are throughput suboptimal, Independence polynomials of circulants with an application to music, Connected domination of regular graphs, The obstructions for toroidal graphs with no \(K_{3,3}\)'s, Linear connectivity forces large complete bipartite minors, A note on acyclic edge coloring of complete bipartite graphs, A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs, Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor, Weighted degrees and heavy cycles in weighted graphs, Spectral preorder and perturbations of discrete weighted graphs, A revival of the girth conjecture, On short cycles through prescribed vertices of a graph, On paths and cycles through specified vertices, Topological paths, cycles and spanning trees in infinite graphs, Formal molecular biology, Dynamic of cyclic automata over \(\mathbb Z^2\), Rooted minor problems in highly connected graphs, Hajós' theorem for list coloring, An existential locality theorem, On graphs whose eternal vertex cover number and vertex cover number coincide, Integral closure of powers of edge ideals and their regularity, Scaled consensus of second-order multi-agent systems based on edge-event driven control, About graph sums, Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants, On the structure of the inverse of non-singular unicyclic graphs, Extremal graphs for Estrada indices, The realizable extension problem and the weighted graph \((K _{3,3}, l)\), Investigation of preparation up to six and \(N\)-atom graph states, Ranking hubs and authorities using matrix functions, Sparsity measure of a network graph: Gini index, Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices, Preferences over consumption and status, Independent sets in Line of Sight networks, Finding the edge ranking number through vertex partitions, Equitable improper choosability of graphs, Graph theory in Coq: minors, treewidth, and isomorphisms, Associated primes of powers of edge ideals, Foam evaluation and Kronheimer-Mrowka theories, Structural properties and hamiltonicity of neighborhood graphs, A neighbour scale fixed approach for influence maximization in social networks, Feedback robustness in structured closed-loop system, On structural parameterizations of the bounded-degree vertex deletion problem, Chromatic number, induced cycles, and non-separating cycles, Two-connected signed graphs with maximum nullity at most two, Null decomposition of bipartite graphs without cycles of length 0 modulo 4, Perfect unit graphs of commutative Artinian rings, Cut vertices in comaximal graph of a commutative Artinian ring, Arbitrary partitionability of product graphs, Acyclic sum-list-colouring of cylinders, A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics, Uniquely pressable graphs: characterization, enumeration, and recognition, Some deterministic and random fixed point theorems on a graph, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, A folk theorem for repeated games played on a network, A flow network analysis of direct balance-sheet contagion in financial networks, Graph minor hierarchies, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, The biorder polytope, Efficient entanglement measure for graph states, The incidence coloring conjecture for graphs of maximum degree 3, On the relationships between zero forcing numbers and certain graph coverings, Planar minimally rigid graphs and pseudo-triangulations, First-order expressibility of languages with neutral letters or: The Crane Beach conjecture, Generalizations of matched CNF formulas, Signed graphs with stable maximum nullity at most two, Characterizing 5-map graphs by 2-fan-crossing graphs, Maximum eccentric connectivity index for graphs with given diameter, Ramsey degrees of bipartite graphs: a primitive recursive proof, On Eulerian and regular perfect path double covers of graphs, Batched bin packing, On lower bounds for the chromatic number in terms of vertex degree, Elementary submodels in infinite combinatorics, Unavoidable parallel minors of regular matroids, Total rainbow connection numbers of some special graphs, Two Fraïssé-style theorems for homomorphism-homogeneous relational structures, The \(k\)-regular induced subgraph problem, Approximating constrained minimum cost input-output selection for generic arbitrary pole placement in structured systems, Mixed partition functions and exponentially bounded edge-connection rank, The generalized minimum branch vertices problem: properties and polyhedral analysis, Complexity of independency and cliquy trees, An exact algorithm for the minimum quartet tree cost problem, Total weight choosability of graphs: towards the 1-2-3-conjecture, Three-dimensional right-angled polytopes of finite volume in the Lobachevsky space: combinatorics and constructions, Compact distributed certification of planar graphs, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Weighting by iteration: iterations of \(n\) variables means based on subdivisions of the standard \((n-1)\)-simplex, Compatible cycles and CHY integrals, Bundling all shortest paths, Level property of ordinary and symbolic powers of Stanley-Reisner ideals, Optimal designs for treatment comparisons represented by graphs, Colouring of cubic graphs by Steiner triple systems, Covering projective planar graphs with three forests, Improper sum-list colouring of 2-trees, Barabasi-Albert trees are hypoenergetic, Skeleton matching polytope: realization and isomorphism, Block-indifference graphs: characterization, structural and spectral properties, SPC product codes, graphs with cycles and Kostka numbers, On the grey obligation rules, On the maxima of Motzkin-Straus programs and cliques of graphs, Graphs with magnetic Schrödinger operators of low corank, Relay placement for two-connectivity, Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference., Congruences of convex algebras., Backdoors to tractable answer set programming, Finding paths in graphs avoiding forbidden transitions, Refined finiteness and degree properties in graphs, About graph unions and intersections, Unmixedness of some weighted oriented graphs, Inference on the structure of gene regulatory networks