Graph Theory

DOI10.1007/978-3-662-53622-3zbMath1375.05002OpenAlexW4245608944MaRDI QIDQ2829286

Publication date: 27 October 2016

Published in: Graduate Texts in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53622-3

Mathematics Subject Classification ID

Ramsey theory (05D10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graph theory (05Cxx)

Related Items

Improved upper bounds on longest-path and maximal-subdivision transversals, ALMOST THEOREMS OF HYPERARITHMETIC ANALYSIS, The minor order of homomorphisms via natural dualities, An algebraic formulation of hypergraph colorings, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, On the zombie number of various graph classes, Tree 3-spanners on generalized prisms of graphs, Non-Gorenstein locus and almost Gorenstein property of the Ehrhart ring of the stable set polytope of a cycle graph, Edge coloring of graphs of signed class 1 and 2, Computing connected-$k$-subgraph cover with connectivity requirement, Detours in directed graphs, On reconfiguration graphs of independent sets under token sliding, A full characterization of invariant embeddability of unimodular planar graphs, An approximation algorithm for the clustered path travelling salesman problem, Listing the bonds of a graph in $\widetilde{O} (n)$-delay, Deletion to scattered graph classes. I: Case of finite number of graph classes, On graph norms for complex‐valued functions, Self‐adjoint and Markovian extensions of infinite quantum graphs, Edge-wise funnel output synchronization of heterogeneous agents with relative degree one, The structure of groups with all proper quotients virtually nilpotent, Maximally edge‐connected realizations and Kundu's k $k$‐factor theorem, Rooted minors and locally spanning subgraphs, Entanglements, On the Erdős–Pósa Property for Long Holes in $\boldsymbol{C_4}$-Free Graphs, Locally Finite ultrametric spaces and labeled trees, Zero-memory graph exploration with unknown inports, Formalising Szemerédi's Regularity Lemma and Roth's Theorem on Arithmetic Progressions in Isabelle/HOL, Solving infinite-domain CSPs using the patchwork property, A survey of parameterized algorithms and the complexity of edge modification, How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks, A Cantor-Bendixson rank for siblings of trees, Induced subgraphs and path decompositions, Colorful graph coloring, Computing maximum matchings in temporal graphs, Hardness of bounding influence via graph modification, Balanced substructures in bicolored graphs, Sequentially swapping tokens: further on graph classes, Random cubic planar maps, Graph product structure for non-minor-closed classes, Local Hadwiger's conjecture, Visibility representations of toroidal and Klein-bottle graphs, The linkedness of cubical polytopes: beyond the cube, Some conditions for Hamiltonian cycles in 1-tough $(K_2 \cup kK_1)$-free graphs, Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC, Covering monotonicity of the limit shapes of first passage percolation on crystal lattices, Succinct data structure for path graphs, Quasidiagonal weighted shifts on directed trees, THE STRENGTH OF AN AXIOM OF FINITE CHOICE FOR BRANCHES IN TREES, Maximizing Graovac-Ghorbani Index of Trees with Fixed Maximum Degree, Parameterized algorithms for eccentricity shortest path problem, Make a graph singly connected by edge orientations, The regularity of almost all edge ideals, Some new algorithmic results on co-secure domination in graphs, Planar graphs with the maximum number of induced 6-cycles, Minimum degree of minimal $(n-10)$-factor-critical graphs, Upper bounds on the acyclic chromatic index of degenerate graphs, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Maximizing Social Welfare in Score-Based Social Distance Games, Minor embedding in broken chimera and derived graphs is NP-complete, Eulerian Spaces, Feedback game on $3$-chromatic Eulerian triangulations of surfaces, Gluing Karcher-Scherk saddle towers. I: Triply periodic minimal surfaces, graph, Unnamed Item, Unnamed Item, Unnamed Item, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Duality Theorems for Blocks and Tangles in Graphs, A note on semicompleteness of graph products of abelian groups, A Formal Model for Polarization under Confirmation Bias in Social Networks, Classes of graphs embeddable in order-dependent surfaces, Period collapse in Ehrhart quasi-polynomials of $\{1,3\}$-graphs, Even circuits in oriented matroids, Application of a Distributed Containment Algorithm: Trajectory Tracking for Mobile Robots, $n$-Arc connected graphs, Geometry and Combinatorics via Right-Angled Artin Groups, Chromatic uniqueness of zero-divisor graphs, Totally ramified rational maps, Digraphs and Variable Degeneracy, Continuous Rendezvous Algorithm for Memoryless Agents with Limited Visibility in the Euclidean Space, THEOREMS OF HYPERARITHMETIC ANALYSIS AND ALMOST THEOREMS OF HYPERARITHMETIC ANALYSIS, UNIT AND UNITARY CAYLEY GRAPHS FOR THE RING OF EISENSTEIN INTEGERS MODULO $n$, Levelness versus almost Gorensteinness of edge rings of complete multipartite graphs, LDPC codes from cubic semisymmetric graphs, Simultaneously dominating all spanning trees of a graph, Throttling for standard zero forcing on directed graphs, Ramsey properties of products of chains, An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength, Properties of Large 2-Crossing-Critical Graphs, Linkedness of Cartesian products of complete graphs, Trees of tangles in infinite separation systems, $k$-apices of minor-closed graph classes. I: Bounding the obstructions, Embedding clique-factors in graphs with low $\ell$-independence number, Parameterized complexity of perfectly matched sets, An approximation algorithm for the clustered path travelling salesman problem, Disjoint cycles covering specified vertices in bipartite graphs with partial degrees, Acyclic chromatic index of chordless graphs, Tuza's Conjecture for Threshold Graphs, Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph, Flexible list colorings in graphs with special degeneracy conditions, Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs, Weak degeneracy of graphs, Nonabelian flows in networks, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Packing Signatures in Signed Graphs, Exploiting Database Management Systems and Treewidth for Counting, Clique-factors in graphs with sublinear -independence number, A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width, Introduction to graph enumerations, About regular graphs, Optimal sufficient requirements on the embedded Ising problem in polynomial time, Connections between graphs and matrix spaces, Large simple $d$-cycles in simplicial complexes, Forbidden subgraphs and 2‐factors in 3/2‐tough graphs, Distinguishing threshold of graphs, Synchronized Planarity with Applications to Constrained Planarity Problems, The Lovász-Cherkassky theorem for locally finite graphs with ends, Even A‐cycles have the edge‐Erdős–Pósa property, Uniformly connected graphs, Interval colorings of graphs—Coordinated and unstable no‐wait schedules, Zero-temperature stochastic Ising model on planar quasi-transitive graphs, The prime submodules hypergraph of a free module of finite rank over a commutative ring, On the complexity of distance-$d$ independent set reconfiguration, Maximal closed set and half-space separations in finite closure systems, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Orientation‐based edge‐colorings and linear arboricity of multigraphs, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: Nets and bulls, Factorizing the Rado graph and infinite complete graphs, Ramsey-type results for path covers and path partitions. II: Digraphs, Formality of cochains on BG$BG$, On bounds of $A_\alpha$-eigenvalue multiplicity and the rank of a complex unit gain graph, Lipschitz-free Spaces on Finite Metric Spaces, On Betti numbers of flag complexes with forbidden induced subgraphs, Unnamed Item, Group-theoretic generalisations of vertex and edge connectivities, Unnamed Item, Nerves, minors, and piercing numbers, The sepr-sets of sign patterns, Examples of 4D, 𝒩 = 2 holoraumy, Parameterized Algorithms for Book Embedding Problems, Infinite-dimensional algebras without simple bases, Tree in forbidden triples generating a finite set of graphs with high connectivity, Flexible List Colorings in Graphs with Special Degeneracy Conditions, Finding Temporal Paths Under Waiting Time Constraints., Properties of graphs specified by a regular language, Unnamed Item, Unnamed Item, Homomorphisms of Cayley graphs and cycle double covers, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, FORBIDDEN TRIPLES GENERATING A FINITE SET OF GRAPHS WITH HIGH CONNECTIVITY, A polynomial kernel for distance-hereditary vertex deletion, Mathematical programming formulations for the alternating current optimal power flow problem, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, Infinite benzenoids, Edge exploration of temporal graphs, Decomposing split graphs into locally irregular graphs, Distributed distance-$r$ covering problems on sparse high-girth graphs, Unnamed Item, On Tuza's conjecture for triangulations and graphs with small treewidth, The finite embeddability property for IP loops and local embeddability of groups into finite IP loops, Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, Travelling on graphs with small highway dimension, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Distributed link scheduling in wireless networks, On perfect annihilator graphs of commutative rings, On Covering Segments with Unit Intervals, Sums of squares and quadratic persistence on real projective varieties, A note on the Gaffney Laplacian on infinite metric graphs, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Sparse hop spanners for unit disk graphs, Consequences of the packing problem, Proof of Halin's normal spanning tree conjecture, Approximately counting locally-optimal structures, Three families of toric rings arising from posets or graphs with small class groups, Hamilton-laceable bi-powers of locally finite bipartite graphs, On Dasgupta's hierarchical clustering objective and its relation to other graph parameters, Graph invariants of the line graph of zero divisor graph of $\mathbb{Z}_n $, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, On a colored Turán problem of Diwan and Mubayi, Aspects of topological approaches for data science, On the feedback number of 3-uniform linear extremal hypergraphs, Linear bounds for cycle-free saturation games, Maximal chains in bond lattices, Many faces of symmetric edge polytopes, Equality of opportunity and integration in social networks, Reconfiguration on nowhere dense graph classes, Consensus and voting on large graphs: an application of graph limit theory, Upper tails via high moments and entropic stability, Purity results for some arithmetically defined measures, Forbidden triples generating a finite set of graphs with minimum degree three, The $\mathbb{Z}_2$-genus of Kuratowski minors, Extremum seeking based fault-tolerant cooperative control for multiagent systems, On a construction by Giudici and Parker on commuting graphs of groups, Harmless sets in sparse classes, Using edge contractions and vertex deletions to reduce the independence number and the clique number, Monochromatic trees in random graphs, On contact graphs of paths on a grid, Metric currents and the Poincaré inequality, Algebraically grid-like graphs have large tree-width, Seminormality, canonical modules, and regularity of cut polytopes, Finding temporal paths under waiting time constraints, Counting linear extensions: parameterizations by treewidth, Existence of a spanning tree having small diameter, Rooted complete minors in line graphs with a Kempe coloring, Enlarging vertex-flames in countable digraphs, Long cycles, heavy cycles and cycle decompositions in digraphs, Proximity semantics for topic-based abstract argumentation, Planarity of Cayley graphs of graph products of groups, Higher cyclic operads, The Dirichlet problem for orthodiagonal maps, Connectivity of cubical polytopes, Vertex-facet assignments for polytopes, Bottleneck subset-type restricted matching problems, Tilings from graph directed iterated function systems, The geometry of partial fitness orders and an efficient method for detecting genetic interactions, A characterization of trees based on edge-deletion and its applications for domination-type invariants, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Parameterized algorithms for conflict-free colorings of graphs, Cliques in hyperbolic random graphs, Throttling for the game of cops and robbers on graphs, Theoretical aspects of equitable partition of networks into sparse modules, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, A new proof of Balinski's theorem on the connectivity of polytopes, Improved bounds on the Ramsey number of fans, Fractal dimension and lower bounds for geometric problems, Unavoidable minors for graphs with large $\ell_p$-dimension, Complexity of tree-coloring interval graphs equitably, Faster algorithms for counting subgraphs in sparse graphs, Simplicity of augmentation submodules for transformation monoids, Distribution of contractible edges and the structure of noncontractible edges having endvertices with large degree in a 4-connected graph, A lower bound on the zero forcing number, Achromatic number and facial achromatic number of connected locally-connected graphs, Induced nets and Hamiltonicity of claw-free graphs, The linkedness of cubical polytopes: the cube, Hitting forbidden induced subgraphs on bounded treewidth graphs, Distance matching extension in cubic bipartite graphs, Analysis on Laakso graphs with application to the structure of transportation cost spaces, On list $k$-coloring convex bipartite graphs, New bounds for Ramsey numbers $R ( K_k - e , K_l - e )$, New constructions of divisible design Cayley graphs, The 2-partially distance-regular graphs such that their second largest local eigenvalues are at most one, A Glazman-Povzner-Wienholtz theorem on graphs, Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy, On the expected number of perfect matchings in cubic planar graphs, Number of distinguishing colorings and partitions, Rigidity, weak mixing, and recurrence in abelian groups, Vague multigraphs, LDPC codes constructed from cubic symmetric graphs, On pro-$p$ groups with quadratic cohomology, Edge-distinguishing of star-free graphs, Analysis of the continuum with surreal numbers, Excluding a ladder, A characterization of graphs with regular distance-2 graphs, Eternal vertex cover on bipartite graphs, Identifiability of local and global features of phylogenetic networks from average distances, Groups of $p$-absolute Galois type that are not absolute Galois groups, Connectivity of triangulation flip graphs in the plane, Reversible Markov decision processes and the Gaussian free field, A tree-of-tangles theorem for infinite tangles, Complexity and approximability of minimum path-collection exact covers, Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs, Antimagic labeling of biregular bipartite graphs, The distance matching extension in $K_{1,k}$-free graphs with high local connectedness, All subgraphs of a wheel are 5-coupled-choosable, A multi-agent model for polarization under confirmation bias in social networks, New limits of treewidth-based tractability in optimization, On the Complexity of Singly Connected Vertex Deletion, On the Parameterized Complexity of the Expected Coverage Problem, Disjoint dijoins for classes of dicuts in finite and infinite digraphs, On algorithmic Coxeter spectral analysis of positive posets, On Ramsey-minimal infinite graphs, A characterization of 2-connected $\{ K_{1 , 3} , N_{3 , 1 , 1} \}$-free non-Hamiltonian graphs, Characterising $k$-connected sets in infinite graphs, Finite rings with Eulerian nilpotent graphs, The damage throttling number of a graph, Finding a path with two labels forbidden in group-labeled graphs, Kernelization and approximation of distance-$r$ independent sets on nowhere dense graphs, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, A fast algorithm for the product structure of planar graphs, Sum-list colouring of unions of a hypercycle and a path with at most two vertices in common, Canonical trees of tree-decompositions, A fast distributed algorithm for $(\Delta+1)$-edge-coloring, Edge-connectivity matrices and their spectra, Abstract separation systems, Tree sets, Gerrymandering on graphs: computational complexity and parameterized algorithms, Feedback vertex set on Hamiltonian graphs, Bears with hats and independence polynomials, Beyond Helly graphs: the diameter problem on absolute retracts, Listen before you link: optimal monitoring rules for communication networks, Labeled trees generating complete, compact, and discrete ultrametric spaces, The agreement distance of unrooted phylogenetic networks, On coherence of graph products of groups and Coxeter groups, The Lovász-Cherkassky theorem in countable graphs, A logical study of group-size based social network creation, Hanani-Tutte for radial planarity. II, Reconfiguration graphs of zero forcing sets, Contractible edges and longest cycles in 3-connected graphs, Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths, Treewidth is a lower bound on graph gonality, A unified existence theorem for normal spanning trees, Planar median graphs and cubesquare-graphs, On the role of 3's for the 1-2-3 conjecture, Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting), Unnamed Item, Parameterized algorithms for book embedding problems, Halin's end degree conjecture, On Euclidean distances and sphere representations, Legendrian weaves: $N$-graph calculus, flag moduli and applications, Splitting groups with cubic Cayley graphs of connectivity two, The Turán number of directed paths and oriented cycles, A study of the generalized outerplanar index of zero-divisor graphs, Unnamed Item, Unnamed Item, Indecomposable continua as Higson coronae, Propagation tree decompositions and linearly independent vertices, Tangle-tree duality in abstract separation systems, On the Block Number of Graphs, Port-Hamiltonian formulation of nonlinear electrical circuits, Equitable list tree-coloring of bounded treewidth graphs, Uniform orderings for generalized coloring numbers, An analogue of Edmonds' branching theorem for infinite digraphs, Upper Bounds on the Graph Minor Theorem, The lattice of cycles of an undirected graph, Approximating Shortest Connected Graph Transformation for Trees, Trees of tangles in abstract separation systems, Unnamed Item, Minimal obstructions for normal spanning trees, Weighted total acquisition, The complexity of counting edge colorings for simple graphs, Approximate bit dependency analysis to identify program synthesis problems as infeasible, Waypoint routing on bounded treewidth graphs, On the weak 2-coloring number of planar graphs, Packing $A$-paths of length zero modulo four, Hamiltonicity via cohomology of right-angled Artin groups, Entire functions arising from trees, Bounded colouring motivated by the limited resource partially concurrent open shop problem, Consecutive colouring of oriented graphs, A Ramsey-type theorem for the matching number regarding connected graphs, Bounds for the spectral radius and energy of extended adjacency matrix of graphs, On a Ramsey--Turán Variant of the Hajnal--Szemerédi Theorem, Realizable ranks of joins and intersections of subgroups in free groups, Monotonic core allocation paths for assignment games, Fermat’s Last Theorem Implies Euclid’s Infinitude of Primes, Divisible design Cayley digraphs, Self-assembly of geometric space from random graphs, Long paths in bipartite graphs and path-bistar bipartite Ramsey numbers, Finding Detours is Fixed-Parameter Tractable, A reduction procedure for the Colin de Verdière number of a graph, Algorithmic networks: central time to trigger expected emergent open-endedness, Ring index of a graph, Packing and Covering Induced Subdivisions, Deleting vertices to graphs of bounded genus, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, How many variables are needed to express an existential positive query?, State-dependent effective interactions in oscillator networks through coupling functions with dead zones, The poset of graphs ordered by induced containment, The firing squad problem revisited, Counting Weighted Independent Sets beyond the Permanent, Euler Digraphs, A Coxeter type classification of one-peak principal posets, In absence of long chordless cycles, large tree-width becomes a local phenomenon, On the basis pair graphs of signed-graphic matroids, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Orientation Ramsey Thresholds for Cycles and Cliques, Limiting Crossing Numbers for Geodesic Drawings on the Sphere