Graph theory (algorithmic, algebraic, and metric problems)

DOI10.1007/BF01086177zbMath0627.05043OpenAlexW2054975725MaRDI QIDQ581419

S. V. Yushmanov, V. P. Kozyrev

Publication date: 1987

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01086177

zbMATH Keywords

surveycolouringsisomorphism problemgraph reconstructiongraph metrics

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (05C99)

Cites Work

• A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs
• A characterization of median graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Medians in median graphs
• A generalization of the Bondy-Chvátal theorem on the k-closure
• Edge-contraction problems
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• NP-completeness of some problems of partitioning and covering in graphs
• An optimal parallel connectivity algorithm
• A Helly theorem for convexity in graphs
• Two theorems on Hamiltonian graphs
• Shortest coverings of graphs with cycles
• Almost all regular graphs are Hamiltonian
• Non-Hamiltonian 3-connected cubic bipartite graphs
• On powers and centers of chordal graphs
• Ensemble convexes dans les graphes. I: Théoremes de Helly et de Radon pour graphes et surfaces
• Graph isomorphism problem
• A note on the complexity of finding regular subgraphs
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests
• Easy and hard bottleneck location problems
• A census of non-reconstructable digraphs. I: Six related families
• The node-deletion problem for hereditary properties is NP-complete
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On the coverings of graphs
• Feasibility conditions for the existence of walk-regular graphs
• A bound on the chromatic number of graphs without certain induced subgraphs
• Coverings of the complete (di-)graph with n vertices by complete bipartite (di-)graphs with n vertices. I
• Generalized k-tuple colorings of cycles and other graphs
• On the decomposition of a graph into stars
• Distance-transitive and distance-regular digraphs
• The central ratio of a graph
• A fast algorithm for finding all shortest paths
• On the reconstruction of separable graphs from elementary contractions
• On a new digraph reconstruction conjecture
• Boolean distance for graphs
• On distance-regularity in graphs
• Bipartite decomposition of complete multipartite graphs
• Partition numbers for trees and ordered sets
• Color-families are dense
• Signed graph coloring
• The diameter of bipartite distance-regular graphs
• Some general constructions of geodetic blocks
• Convexity in graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Longest cycles in r-regular r-connected graphs
• Forbidden subgraphs and Hamiltonian properties and graphs
• Chromatic invariants of signed graphs
• Hamiltonian paths in vertex-symmetric graphs of order 5p
• An eigenvector condition for reconstructibility
• n-tuple colorings and associated graphs
• A note on a paper by D. Seinsche
• On claw-decomposition of complete graphs and complete bigraphs
• Chromatic number and skewness
• Pairs of Hamiltonian circuits in 5-connected planar graphs
• Strongly regular graphs
• Chromatic number and girth
• The edge reconstruction hypothesis is true for graphs with more than \(n\cdot \log_2\,n\) edges
• A sufficient condition for Hamiltonian circuits
• On the distance matrix of a tree
• Multicolorings, measures and games on graphs
• Acyclic orientations of a graph and the chromatic and independence numbers
• A method in graph theory
• Automorphic graphs and the Krein condition
• On reconstructing graphs from their sets of subgraphs
• Reconstructing trees from two point deleted subtrees
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• A note on the complexity of the chromatic number problem
• On metric properties of certain clique graphs
• r-tuple colorings of uniquely colorable graphs
• Some simplified NP-complete graph problems
• A proof of the four color theorem
• Panconnected graphs. II
• Note sur le problème de Ulam
• Point deletions of outerplanar blocks
• Riemann's hypothesis and tests for primality
• Mean distance in a graph
• New flip-flop constructions for hypohamiltonian graphs
• Covering the vertex set of a graph with subgraphs of smaller degree
• A bound on the chromatic number of a graph
• On graphs with Hamiltonian squares
• On the chromatic index of almost all graphs
• A remark on two sufficient conditions for Hamilton cycles
• Some graphs with chromatic number three
• On claw-decomposition of a complete multi-partite graph
• Distance matrix polynomials of trees
• Another bound on the chromatic number of a graph
• A remark on the time complexity of the subtree problem
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• On partitions of graphs into trees
• Path coverings of the vertices of a tree
• Spectral conditions for the reconstructibility of a graph
• The structure of median graphs
• A note on the graph isomorphism counting problem
• On the chromatic number of skew graphs
• Set colourings of graphs
• On acyclic colorings of planar graphs
• Graph 2-isomorphism is NP-complete
• The reconstruction of maximal planar graphs. II: Reconstruction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The square of a block is Hamiltonian connected
• Pancyclic graphs and a conjecture of Bondy and Chvatal
• On the NP-hardness of edge-deletion and -contraction problems
• An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
• Distance-regular graphs and (s,c,a,k)-graphs
• On the existence of Hamiltonian cycles in a class of random graphs
• Some applications of Vizing's theorem to vertex colorings of graphs
• The chromatic number and other functions of the lexicographic product
• On pancyclic digraphs
• Some basic observations on Kelly's conjecture for graphs
• Reconstruction of a tree from its homomorphic images and other related transforms
• The reconstruction of outerplanar graphs
• On the chromatic index of outerplanar graphs
• Sufficient conditions for a graph to be Hamiltonian
• Representation of a tree with p hanging vertices by 2p-3 elements of its distance matrix
• A graph polynomial and its applications
• Eigenvalues and partitionings of the edges of a graph
• Theory of path length distributions. I
• Covering the vertices of a graph by vertex-disjoint paths
• On a property of the class of n-colorable graphs
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Parallel computations on graphs
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• MinimumK-hamiltonian graphs
• Recognizing decomposable graphs
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• On computing the connectivities of graphs and digraphs
• A quick method for finding shortest pairs of disjoint paths
• Shortest-path algorithms: Taxonomy and annotation
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Isomorphism of graphs which are pairwise k-separable
• An algorithm for construction of ak-connected graph with minimum number of edges and quasiminimal diameter
• Clique Covering of Graphs IV. Algorithms
• On the sum of all distances in a graph or digraph
• Geodesic subgraphs
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• Estimation of sparse hessian matrices and graph coloring problems
• The linear arboricity of some regular graphs
• Improving the performance guarantee for approximate graph coloring
• Node-Deletion NP-Complete Problems
• Centers to centroids in graphs
• Note on a new coloring number of a graph
• A characterization of ptolemaic graphs
• Edge‐reconstruction of planar graphs with minimum valency 5
• Note on Choudum's “chromatic bounds for a class of graphs”
• Medians of arbitrary graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Centers of 2–Trees
• Edge-reconstruction of 4-connected planar graphs
• ON THE EDGE-RECONSTRUCTION OF GRAPHS WHICH TRIANGULATE SURFACES
• Random Graph Isomorphism
• Some NP-Complete Problems Similar to Graph Isomorphism
• On the N-Clique Chromatic Number of Complementary Graphs
• The Philosophical Implications of the Four-Color Problem
• Partitioning trees: Matching, domination, and maximum diameter
• Edge-Deletion Problems
• The tree-covering number of a graph
• The NP-Completeness of Edge-Coloring
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Covering and packing in graphs IV: Linear arboricity
• Linear-time computability of combinatorial problems on series-parallel graphs
• New lower bound techniques for VLSI
• Degree sets for homogeneously traceable non-Hamiltonian graphs
• A class of geodetic blocks
• Cyclically 5-edge-connected cubic planar graphs and shortness coefficients
• On the complexity of the general coloring problem
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
• A Generalization of the 5-Color Theorem
• Complementary Graphs and Total Chromatic Numbers
• Generalized Graph Colorations
• The Complexity of Near-Optimal Graph Coloring
• On the optional hamiltonian completion problem
• Distance in graphs
• Every planar map is four colorable
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Some recent results in hamiltonian graphs
• The falsity of the reconstruction conjecture for tournaments
• Finding a Maximum Independent Set
• CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph reconstruction—a survey
• An acyclic analogue to Heawood's theorem
• Nearly acyclic graphs are reconstructible
• Computer reconstruction of small graphs
• On the Genus of Graphs with Lick-White Number k
• Determining the Stability Number of a Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Determining the Chromatic Number of a Graph
• Centers of maximal outerplanar graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• An upper bound for the path number of a graph
• The complexity of finding maximum disjoint paths with length constraints
• An algorithm for finding a large independent set in planar graphs
• 2-Isomorphic Graphs
• Graphs in which every path is contained in a Hamilton path.
• On planar geodetic graphs
• On Reconstructing a Graph
• Tournaments That Admit Exactly One Hamiltonian Circuit
• On Hamiltonian Walks in Graphs
• Geodetic graphs of diameter two

This page was built for publication: Graph theory (algorithmic, algebraic, and metric problems)