A Theorem on Planar Graphs
From MaRDI portal
Publication:3231816
DOI10.2307/1992980zbMath0070.18403OpenAlexW4245155377WikidataQ56209819 ScholiaQ56209819MaRDI QIDQ3231816
Publication date: 1956
Full work available at URL: https://doi.org/10.2307/1992980
Related Items
Guarding rectangular art galleries, Path partitioning planar graphs of girth 4 without adjacent short cycles, Spanning Eulerian subgraphs of bounded degree in triangulations, A unified approach to visibility representations of planar graphs, Toughness and Hamiltonicity of a class of planar graphs, Cycles in 4-connected planar graphs, Every 4-connected line graph of a planar graph is Hamiltonian, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, Two-page book embeddings of 4-planar graphs, Protecting convex sets, Every 5-connected planar triangulation is 4-ordered Hamiltonian, Greedy drawings of triangulations, Graph-theoretical conditions for inscribability and Delaunay realizability, Chords of longest circuits in locally planar graphs, Dominating plane triangulations, The circumference of a graph with no \(K_{3,t}\)-minor, Hamiltonicity and colorings of arrangement graphs, Random triangulations of the plane, The complexity of recognizing tough cubic graphs, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, 2-connected spanning subgraphs with low maximum degree in locally planar graphs, Tutte cycles in circuit graphs, Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs, On 2-connected spanning subgraphs with low maximum degree, Hamiltonian cycles in polyhedral maps, Intersecting longest paths, Interval matroids and graphs, Lower bounds on the cardinality of the maximum matchings of planar graphs, Bounding tree-width via contraction on the projective plane and torus, The circumference of a graph with no \(K_{3,t}\)-minor. II, Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs, On regular graphs and Hamiltonian circuits, including answers to some questions of Joseph Zaks, An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs, Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Dynamic graph-based search in unknown environments, Arc diagrams, flip distances, and Hamiltonian triangulations, Edge-disjoint Hamilton cycles in 4-regular planar graphs, The smallest 2-connected cubic bipartite planar nonhamiltonian graph, When m vertices in a k-connected graph cannot be walked round along a simple cycle, Subgraphs of graphs on surfaces with high representativity, On k-path Hamiltonian maximal planar graphs, Hamiltonian knot projections and lengths of thick knots., The matching extendability of surfaces, Spanning closed walks and TSP in 3-connected planar graphs, On the obfuscation complexity of planar graphs, Complete colorings of planar graphs, Polyhedra with few 3-cuts are Hamiltonian, Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs, Guthrie's problem: new equivalences and rapid reductions, Spanning trees with nonseparating paths, Minimal \(k\)-connected non-Hamiltonian graphs, Flips in planar graphs, Non-Hamiltonian triangulations with distant separating triangles, Extending matchings in planar graphs. IV, On existence theorems, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs, Hamiltonian cycles in 4-connected plane triangulations with few 4-separators, Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs, A note on 3-connected cubic planar graphs, Pairs of Hamiltonian circuits in 5-connected planar graphs, What is on his mind?, A note on traversing specified vertices in graphs embedded with large representativity, Über n-fach zusammenhängende Eckenmengen in Graphen, Covering planar graphs with forests, Pairs of edge-disjoint Hamiltonian circuits, Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs, Connectivity, genus, and the number of components in vertex-deleted subgraphs, Bridges and Hamiltonian circuits in planar graphs, Hamiltonian properties of polyhedra with few 3-cuts. A survey, A new proof that 4-connected planar graphs are Hamiltonian-connected, Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27, Hamiltonian circuits in prisms over certain simple 3-polytopes, Matching points with squares, Metamathematical approach to proving theorems of discrete mathematics, Maximal Hamiltonian cycles in squares of graphs, 3-trees with few vertices of degree 3 in circuit graphs, Long cycles in 4-connected planar graphs, Maximum bipartite subgraphs of cubic triangle-free planar graphs, 4-connected polyhedra have at least a linear number of Hamiltonian cycles, Long cycles through specified vertices in a graph, On spanning subgraphs of 4-connected planar graphs, Cycle spectra of contraction-critically 4-connected planar graphs, Vertex degrees and 2-cuts in graphs with many Hamiltonian vertex-deleted subgraphs, Vertices of small degree in uniquely Hamiltonian graphs, A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs, Hamiltonicity in vertex envelopes of plane cubic graphs, An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs, Some remarks on Jaeger's dual-hamiltonian conjecture, On Hamiltonian cycles in 4- and 5-connected plane triangulations, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Surfaces, tree-width, clique-minors, and partitions, Long cycles in graphs on a fixed surface, Long cycles in 3-connected graphs, A survey of the asymptotic behaviour of maps, Hamiltonian cycles in cubic 3-connected bipartite planar graphs, The number of cycles in 2-factors of cubic graphs, Small cycle double covers of 4-connected planar graphs, Extending matchings in graphs: A survey, Longest cycles in 3-connected cubic graphs, On 2-factors splitting an embedded graph into two plane graphs, Toughness and nonhamiltonicity of polyhedral graphs, Counting Hamiltonian cycles in planar triangulations, The \(k\)-subconnectedness of planar graphs, Unnamed Item, Asymptotic dimension of planes and planar graphs, The number of defective colorings of graphs on surfaces, A survey on book-embedding of planar graphs, Hamilton cycles in line graphs of 3-hypergraphs, On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs, Each maximal planar graph with exactly two separating triangles is Hamiltonian, 5-Connected Toroidal Graphs are Hamiltonian-Connected, Every 4-Connected Graph with Crossing Number 2 is Hamiltonian, Characterization of \((m, n)\)-linked planar graphs, Polytopes, graphs, and complexes, Cycles through all finite vertex sets in infinite graphs, On the structure of essentially-highly-connected polyhedral graphs, Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian, Strongly even cycle decomposable 4-regular line graphs, Computing Tutte Paths, Hamiltonian Cycles in 4-Connected Planar and Projective Planar Triangulations with Few 4-Separators, On the circumference of 3-connected cubic triangle-free plane graphs, Construction of Barnette graphs whose large subgraphs are non-Hamiltonian, On graphs with minimal distance signless Laplacian energy, Upper and Lower Bounds on Long Dual Paths in Line Arrangements, Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs, Find subtrees of specified weight and cycles of specified length in linear time, At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles, \([a,b\)-factors of graphs on surfaces], Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices, On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs, Lightweight paths in graphs, Unnamed Item, Rooted minors and locally spanning subgraphs, Path eccentricity of graphs, A note on Hamiltonian cycles in planar graphs, Planar Digraphs of Digirth Four are 2-Colorable, K2‐Hamiltonian graphs: II, Improving upper bounds for the distinguishing index, Local neighbor-distinguishing index of graphs, Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey, Colored anchored visibility representations in 2D and 3D space, Embedding knots and links in an open book II. Bounds on arc index, Cycle traversability for claw-free graphs and polyhedral maps, Prescribed edges and forbidden edges for a cycle in a planar graph, On longest cycles in essentially 4-connected planar graphs, A counterexample to prism-Hamiltonicity of 3-connected planar graphs, On longest cycles in essentially 4-connected planar graphs, Plane Triangulations Without Spanning 2-Trees, Problems on pairs of trees and the four colour problem of planar graphs, Unnamed Item, Path partitioning planar graphs with restrictions on short cycles, A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs, Hamilton paths in toroidal graphs, Unnamed Item, Unnamed Item, Independent sets in triangle-free cubic planar graphs, Toughness in graphs -- a survey, Tough graphs and Hamiltonian circuits. (Reprint), 2- and 3-factors of graphs on surfaces, Contractible Hamiltonian cycles in triangulated surfaces, 2-edge-Hamiltonian-connectedness of 4-connected plane graphs, Graph theory, Cycles in 5-connected triangulations, Criticality of counterexamples to toroidal edge-Hamiltonicity, Hamilton circles in infinite planar graphs, Shortness coefficient of cyclically 4-edge-connected cubic graphs, Infinite Hamilton cycles in squares of locally finite graphs, Sulla tracciabilita' di grafi finiti su superficie compatte, Alcuni sviluppi sulla teoria relativa dei singrammi finiti, Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Reconfiguration of connected graph partitions via recombination, Reconfiguration of connected graph partitions via recombination, On the genus and connectivity of Hamiltonian graphs, Hamiltonian lines in infinite graphs with few vertices of smll valency, Number of Hamiltonian Cycles in Planar Triangulations, Book Embedding of Graphs on the Projective Plane, Rotation Distance, Triangulations, and Hyperbolic Geometry, Structure and pancyclicity of maximal planar graphs with diameter two, Tough graphs and Hamiltonian circuits., Vertices missed by longest paths or circuits, Hamiltonian cycles in bipartite quadrangulations on the torus, Unnamed Item, 1-Planar Graphs, Spanning trees in 3-connected K3,t-minor-free graphs, Hamilton cycles in 6-connected claw-free graphs (Extended abstract), On Hypohamiltonian and Almost Hypohamiltonian Graphs, Chvátal’s t 0-Tough Conjecture, Regular non-Hamiltonian polyhedral graphs, Disjoint paths, planarizing cycles, and spanning walks, On the Hamiltonian property hierarchy of 3-connected planar graphs, $K_2$-Hamiltonian Graphs: I, Tutte paths and long cycles in circuit graphs, 4-connected projective-planar graphs are Hamiltonian-connected, Geometric biplane graphs. II: Graph augmentation, Distribution of subtree sums, Equivalence of Jackson's and Thomassen's conjectures, Uniquely Hamiltonian Graphs of Minimum Degree 4
Cites Work
