Publication:5422499

Publication date: 22 October 2007

planar graphs; regularity lemma; Ramsey theory; matchings; probabilistic method; cliques; stable sets; four-colour problem; electrical networks; edge colourings; vertex colourings; map colourings; hamilton cycles; basic graph theory: trees; coverings and packings in directed graphs; cycles: nonseparable graphs: tree-search algorithms; flows in networks: complexity of algorithms: connectivity; integer flows and coverings

Mathematics Subject Classification ID

05-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics

05Cxx: Graph theory

Related Items

A search problem on graphs which generalizes some group testing problems with two defectives, The maximum number of diagonals of a cycle in a block and its extremal graphs, A spectral method for concordant polyhedral faces, Graph whose edges are in small cycles, On minimal neighbourhood-connected graphs, A matching game, Cycle bases from orderings and coverings, Long cycles in subgraphs with prescribed minimum degree, Tree-partitions of infinite graphs, The spectrum of maximal sets of one-factors, Maximal cycles in graphs, Personnel placement in a fuzzy environment, On the 2-extendability of planar graphs, Algebraic multiplicity of the eigenvalues of a tournament matrix, On cycle double covers of line graphs, Graphs of maximum diameter, Dominating cycles in regular 3-connected graphs, The degree sequence is reconstructible from \(n-1\) cards, Unimodular equivalence of graphs, Cycles through edges in cyclically \(k\)-connected cubic graphs, The number of edges in a maximum cycle-distributed graph, On cages with given degree sets, On 3-connected graphs with contractible edge covers of size \(k\), Hajós' conjecture and small cycle double covers of planar graphs, Cycles containing many vertices of large degree, A graph-theoretic heuristic for designing loop-layout manufacturing systems, On the integral plane two-commodity flow problem, Julius Petersen's theory of regular graphs, Matching theory -- a sampler: From Dénes König to the present, On the structure of locally semicomplete digraphs, Broadcasting in DMA-bound bounded degree graphs, Cyclomatic numbers of connected induced subgraphs, Some results on visibility graphs, Duality in graph families, Nowhere-zero 3-flows of highly connected graphs, Hamilton cycles in regular 3-connected graphs, Degree constrained tree embedding into points in the plane, Fractional arboricity, strength, and principal partitions in graphs and matroids, Processor interconnection networks from Cayley graphs, Stability number of bull- and chair-free graphs, General vertex disjoint paths in series-parallel graphs, Distributions on bicoloured binary trees arising from the principle of parsimony, Unidirectional star graphs, Complexity of path-forming games, Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs, Hamiltonian graphs involving neighborhood intersections, A construction for equidistant permutation arrays of index one, A short proof of Meyniel's theorem, A remark on two sufficient conditions for Hamilton cycles, Planar cubic hypohamiltonian and hypotraceable graphs, On separating cycles in graphs, Coverings by minimal transversals, The structure of median graphs, On spanning subgraphs of 4-connected planar graphs, Invariant groups on equivalent crystallizations, An adaptive, multiple restarts neural network algorithm for graph coloring, Optimal labellings of rooted directed trees, A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges, A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis, On testing consecutive-ones property in parallel, A two-person game on graphs where each player tries to encircle his opponent's men, A splitting theorem for transitive maps, Forbidden subgraphs, stability and hamiltonicity, The acyclic disconnection of a digraph, A note on covering the edges of a graph with bonds, Pancyclicity of claw-free Hamiltonian graphs, Domination number and neighbourhood conditions, Path factorizations of complete multipartite graphs, A local independence number condition for \(n\)-extendable graphs, A note on the lower bounds of signed domination number of a graph, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Two path extremal graphs and an application to a Ramsey-type problem, A generalization of Fan's condition and forbidden subgraph conditions for hamiltonicity, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, A characterization of uniquely vertex colorable graphs using minimal defining sets, Another cycle structure theorem for Hamiltonian graphs, On the distribution of eigenvalues of graphs, Some Ore-type conditions for the existence of connected \([2,k\)-factors in graphs], The uniformity space of hypergraphs and its applications, On the structure of minimally \(n\)-extendable bipartite graphs, A new upper bound on the number of edges in a geodetic graph, The number of removable edges in 3-connected graphs, A note on \(K_ 4\)-closures in hamiltonian graph theory, Long cycles, degree sums and neighborhood unions, On the complexity of recognizing tough graphs, A closure concept based on neighborhood unions of independent triples, On dominating and spanning circuits in graphs, A generalization of Ore's Theorem involving neighborhood unions, Factoring distance matrix polynomials, The size of a minimum five-chromatic \(K_ 4\)-free graph, On the size of graphs with all cycles having distinct length, A fast algorithm for maximum integral two-commodity flow in planar graphs, Modeling paradigms for discrete event simulation, On the construction of regular minimal broadcast digraphs, On simple MCD graphs containing a subgraph homeomorphic to \(K_ 4\), Sharp bound of the \(k\)th eigenvalue of trees, Packing pentagons into complete graphs: How clumsy can you get?, Maximality of the cycle code of a graph, Lower bounds for constant degree independent sets, Collapsing and lifting for the cut cone, Extending matchings in graphs: A survey, On extremal graphs without compatible triangles or quadrilaterals, On \(m\)-centers in \(P_ t\)-free graphs, Sharing jugs of wine, Database placement in communication networks for minimizing the overall transmission cost, The joint sum of graceful trees, Star chromatic number of triangle-free planar graphs, More facets from fences for linear ordering and acyclic subgraph polytopes, A rounding algorithm for integer programs, Decompositions into linear forests and difference labelings of graphs, Subgraphs, closures and hamiltonicity, Hamiltonicity of bipartite biclaw-free graphs, Hamiltonicity of a type of interchange graphs, Factors of trees, Regular factors in vertex-deleted subgraphs of regular graphs, New classes of Berge perfect graphs, Polyhedral structure and properties of a model for layout design, Obstruction set isolation for the gate matrix layout problem, Strongly well-covered graphs, Graphs and digraphs with given girth and connectivity, The number of cycles in a Hamilton graph, Neighborhood unions and Hamiltonian properties, A problem of Füredi and Seymour on covering intersecting families by pairs, Broadcasting on recursively decomposable Cayley graphs, A note on the minimum cut cover of graphs, Relating path coverings to vertex labellings with a condition at distance two, Enumeration of graph embeddings, Longest cycles in threshold graphs, The 3 and 4-dichromatic tournaments of minimum order, On Kotzig's conjecture for graphs with a regular path-connectedness, Long cycles in graphs containing a 2-factor with many odd components, Algebraic graph theory without orientation, On the Steiner ratio in 3-space, Rooted routing in the plane, Bounds on the largest eigenvalues of trees with a given size of matching, Enumeration of 2-connected loopless 4-regular maps on the plane, The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings, Drawing outerplanar minimum weight triangulations, A note on alternating cycles in edge-coloured graphs, A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian, Graph-theoretical conditions for inscribability and Delaunay realizability, A proof of a conjecture about \(D_ \lambda\)-paths in graphs with large neighborhood unions, Recursively decomposable well-covered graphs, A classification of locally semicomplete digraphs, The complexity of restricted graph homomorphisms, Dirac's minimum degree condition restricted to claws, Defining sets in vertex colorings of graphs and latin rectangles, Euler tours and a game with dominoes, On spanning 2-trees in a graph, Hamilton paths in \(Z\)-transformation graphs of perfect matchings of hexagonal systems, Characterization of products of trees and grids, On \(k\)-strong and \(k\)-cyclic digraphs, Chromaticity of the complements of paths and cycles, Paths and cycles in extended and decomposable digraphs, A note on the minimum size of a vertex pancyclic graph, Claw-free graphs---a survey, Matching extension in \(K_{1,r}\)-free graphs with independent claw centers, Path partition number in tough graphs, \(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs, The chromatic numbers of distance graphs, Hamiltonicity of 2-connected claw-center independent graphs, Connected \([k,k+1\)-factors of graphs], Lower bounds of length of longest cycles in graphs involving neighborhood unions, A generalization of Bondy's and Fan's sufficient conditions for Hamiltonian graphs, On a closure concept in claw-free graphs, Hook immanantal inequalities for Laplacians of trees, Matching extension and minimum degree, Proper interval graphs and the guard problem, A special \(k\)-coloring for a connected \(k\)-chromatic graph, Maximum induced matchings in graphs, Cycles through subsets with large degree sums, Embeddings of \(m\)-cycle systems and incomplete \(m\)-cycle systems: \(m\leq 14\), A new method for proving chromatic uniqueness of graphs, Remarks on the size of critical edge-chromatic graphs, A nice class for the vertex packing problem, Rectangle-visibility representations of bipartite graphs, An application of difference sets to a problem concerning graphical codes, Subdivisions in planar graphs, A bibliography on chromatic polynomials, Optimal packing of induced stars in a graph, A simple construction of high representativity triangulations, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, A fast algorithm for the minimax flow problem with 0/1 weights, The \(\beta\)-assignment problem in general graphs, Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three, The complexity of recognizing tough cubic graphs, A measure of 2D shape-of-object dissimilarity, Wiener number of hexagonal jagged-rectangles, Competition numbers of graphs with a small number of triangles, The point-to-point connection problem - analysis and algorithms, Maximum genus and maximum nonseparating independent set of a 3-regular graph, Apex graphs with embeddings of face-width three, Embedding partial extended triple systems and totally symmetric quasigroups, Supereulerian graphs, independent sets, and degree-sum conditions, On contractible and vertically contractible elements in 3-connected matroids and graphs, The intersection problem for star designs, The pagenumber of toroidal graphs is at most seven, Adjacency of vertices of the complete pre-order polytope, The spread of \(K_n\), Eulerian subgraphs containing given vertices and hamiltonian line graphs, A Chvátal--Erdős type condition for pancyclability, Independence number and vertex-disjoint cycles, Bipartite graphs with every matching in a cycle, Vertex pancyclicity in quasi claw-free graphs, Connected \((n,m)\)-graphs with minimum and maximum zeroth-order general Randić index, Characterizing defect \(n\)-extendable bipartite graphs with different connectivities, On interval edge colorings of \((\alpha ,\beta )\)-biregular bipartite graphs, Algorithms for long paths in graphs, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Contractions of 6-connected toroidal graphs, Reconstructing degree sequences from k-vertex-deleted subgraphs, Picture iteration and picture ambiguity, Reconstructing graphs from cut-set sizes, Coloring algorithms for \(K_ 5\)-minor free graphs, A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle, On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph, Two classes of chromatically unique graphs, A 2-categorical pasting theorem, Estimations for the domination number of a graph, Existence of graphs with specified cycle lengths, On some conjectures on cubic 3-connected graphs, Hamiltonicity of tree-like graphs, On two dual classes of planar graphs, An upper bound on buffer size for join operation using nonclustered indexes, Recognizing tough graphs is NP-hard, Lifting facets of the cut polytope, The 2nd-order conditional 3-coloring of claw-free graphs, Paths in circuit graphs of matroids, The expected hitting times for finite Markov chains, A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class, Graph connectivity, partial words, and a theorem of Fine and Wilf, The Ramsey numbers \(R(C_m,K_7)\) and \(R(C_7,K_8)\), On the rank of a cograph, On minimally circular-imperfect graphs, A sharp upper bound on the spectral radius of weighted graphs, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Plane graphs without cycles of length 4, 6, 7 or 8 are 3-colorable, Hamilton cycle decompositions of the tensor product of complete multipartite graphs, A complete solution to the chromatic equivalence class of graph \(\overline {B_{n-7,1,3}}\), Full friendly index sets of \(P_2 \times P_n\), Authentication codes and bipartite graphs, Hamilton paths in \(\{K_{1,4},K_{1,4}+e\}\)-free graphs, On \(s\)-Hamiltonian-connected line graphs, Subdivisions of graphs: A generalization of paths and cycles, Long paths with endpoints in given vertex-subsets of graphs, Extra edge connectivity and isoperimetric edge connectivity, Ordering trees with \(n\) vertices and matching number \(q\) by their largest Laplacian eigenvalues, The \(s\)-Hamiltonian index, Some topological properties of folded Petersen graph, Ore-condition and \(Z_3\)-connectivity, The Ramsey numbers for stars of even order versus a wheel of order nine, Hamiltonian-connected graphs, K-restricted edge connectivity for some interconnection networks, The maximum fuzzy weighted matching models and hybrid genetic algorithm, Convex drawings of graphs with non-convex boundary constraints, Laplacian spectral radius of trees with given maximum degree, On eigensharp and almost eigensharp graphs, Clique partitions of complements of forests and bounded degree graphs, Minimally restricted edge connected graphs, On tricyclic graphs of a given diameter with minimal energy, Nowhere-zero 3-flows in triangularly connected graphs, Proof of a conjecture on \(k\)-tuple domination in graphs, On the spanning connectivity and spanning laceability of hypercube-like networks, The linear arboricity of planar graphs with no short cycles, Circulant tournaments of prime order are tight, Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks, Hamiltonian properties of triangular grid graphs, Degree sum and nowhere-zero 3-flows, The number of vertices of degree 7 in a contraction-critical 7-connected graph, Edge covered critical multigraphs, The hamiltonian index of a 2-connected graph, Degree sequence and supereulerian graphs, Radius and subpancyclicity in line graphs, Bipartite matching extendable graphs, Some remarks on \(\lambda _{p,q}\)-connectedness, The \(*\)-closure for graphs and claw-free graphs, Degree conditions on induced claws, Some properties of contraction-critical 5-connected graphs, A note on the dominating circuit conjecture and subgraphs of essentially 4-edge-connected cubic graphs, Graphs with the second largest number of maximal independent sets, Cycles through 4 vertices in 3-connected graphs, A sufficient condition for pancyclability of graphs, The connectivity of a graph and its complement, Some three-color Ramsey numbers, \(R(P_4,P_5,C_k)\) and \(R(P_4,P_6,C_k)\), Every line graph of a 4-edge-connected graph is \(\mathbf Z_3\)-connected, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, On the combinatorial structure of a class of \(\left[ \binom m 2, \binom{m-1}{2}, 3\right\) shortened Hamming codes and their dual-codes], On extremal unicyclic molecular graphs with maximal Hosoya index, A note on list improper coloring of plane graphs, The Ramsey number for a cycle of length six versus a clique of order eight, On mod \((2p+1)\)-orientations of graphs, Complexity of conditional colorability of graphs, Extremal Hosoya index and Merrifield-Simmons index of hexagonal spiders, The neighbour-scattering number can be computed in polynomial time for interval graphs, On the bipanpositionable bipanconnectedness of hypercubes, The subdivision-constrained minimum spanning tree problem, On the inapproximability of independent domination in \(2P_3\)-free perfect graphs, Generalized honeycomb torus, Ring embedding in faulty pancake graphs, Minimizing a class of unicyclic graphs by means of Hosoya index, Fuzzy quadratic minimum spanning tree problem, STS-graphs of perfect codes mod kernel, On problems and conjectures on adjointly equivalent graphs, The super connectivity of the pancake graphs and the super laceability of the star graphs, On T-joins and odd factors, Vector representations of graphs, On some extremal connectivity results for graphs and matroids, On factors with given components, Paired-domination in inflated graphs, The pagenumber of the class of bandwidth-k graphs is \(k-1\), Iterative improvement of vertex covers, The maximal \(f\)-dependent set problem for planar graphs is in NC, On the point-to-point connection problem, Element perturbation problems of optimum spanning trees with two-parameter objectives, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Graph theoretic aspects of maximizing the spectral radius of nonnegative matrices, A note on the number of perfect matchings of bipartite graphs, The Wiener number of the hexagonal net, Spanning closed trails in graphs, Packings and perfect path double covers of maximal planar graphs, The cordiality of one-point union of \(n\) copies of a graph, A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices, Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm, Covering the complete graph with plane cycles, On the complexity of colouring by superdigraphs of bipartite graphs, Transforming eulerian trails, Cycle covers of cubic multigraphs, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, On Hamiltonian claw-free graphs, Largest planar graphs of diameter two and fixed maximum degree, The covering radius of the cycle code of a graph, Planar graphs with no 6-wheel minor, \(P_{2p}\)-factorization of a complete bipartite graph, On a problem concerning tolerance graphs, \(p\)-competition numbers, The Laplacian spectrum of a mixed graph, Local ratio with negative weights., Characterization of networks supporting multi-dimensional linear interval routing schemes, Invariant factors of graphs associated with hyperplane arrangements, Some remarks on Hajós' conjecture, Hyper Hamiltonian laceability on edge fault star graph, Large Isaacs' graphs are maximally non-Hamilton-connected, Regular factors of line graphs, On Ringeisen's isolation game, A basis for the cycle space of a 2-connected graph, The convex weighting of a graph and an alternative definition of a matroid, A successful algorithm for solving directed Hamiltonian path problems, The complexity of completing partial Latin squares, Comparison of mean distance in superposed networks, Infinite generalized friendship graphs, Interval-regular graphs, Interval-regular graphs of diameter two, On minor-minimally-connected matroids, Acyclic join dependency and data base projections, Relations between parameters of a graph, On hamiltonian line graphs and connectivity, Sufficient conditions for a graph to have factors, A Chvátal-Erdős condition for (t,t)-factors in digraphs using given arcs, A transposition factorization of walk-permutations in graphs, Label-connected graphs and the gossip problem, The number of cycles in 2-factors of cubic graphs, An upper bound on the shortness exponent of 1-tough, maximal planar graphs, Fractional total colouring, Canonical equation sets for classes of concordant polytopes, Some sufficient conditions for a graph to be of \(C_f\) 1, Nowhere-zero \(Z_3\)-flows through \(Z_3\)-connectivity, Spanning trails containing given edges, Group connectivity of graphs with diameter at most 2, Chords of longest circuits in locally planar graphs, Minimum energy on trees with \(k\) pendent vertices, The number of \(k\)-colorings of a graph on a fixed surface, Rainbowness of cubic plane graphs, Hajós' conjecture for line graphs, Contractions, cycle double covers, and cyclic colorings in locally connected graphs, Distance irredundance and connected domination numbers of a graph, List edge and list total colorings of planar graphs without 4-cycles, A characterization of maximal non-\(k\)-factor-critical graphs, The new methods for constructing matching-equivalence graphs, Hadwiger's conjecture for circular colorings of edge-weighted graphs, How to contract an essentially 6-connected graph to a 5-connected graph, The largest eigenvalue of unicyclic graphs, On the spanning connectivity of graphs, On unimodular graphs, Minimizing the Laplacian eigenvalues for trees with given domination number, Edge-bipancyclicity of star graphs under edge-fault tolerant, Incremental assignment problem, An inequality on graph spectra, Gridline indifference graphs, Degree conditions for Hamiltonicity: counting the number of missing edges, A generalization of Dirac's theorem on cycles through \(k\) vertices in \(k\)-connected graphs, A note on the computational complexity of graph vertex partition, Spectral radius of graphs with given matching number, The Ramsey numbers for a cycle of length six or seven versus a clique of order seven, Hamiltonicity of complements of middle graphs, Quadrangularly connected claw-free graphs, An analogue of Dirac's theorem on circular super-critical graphs, Many 3-colorings of triangle-free planar graphs, A constructive characterization of 3-connected triangle-free graphs, Homomorphisms and edge-colourings of planar graphs, A sufficient condition for cyclability in directed graphs, Disjoint triangles and quadrilaterals in a graph, Sphere-of-influence graphs using the sup-norm, Tree spanners in planar graphs, On disjoint chains of subsets, On mixed Ramsey numbers, Amenable colorings, Unextendible product bases, Disproving a conjecture on planar visibility graphs, Neighborhood unions and regularity in graphs, Partitioning vertices of 1-tough graphs into paths, Independent triangles covering given vertices of a graph, On matroid connectivity, The spread of the spectrum of a graph, On mixed Ramsey numbers, On the visibility graph of convex translates, A degree condition of 2-factors in bipartite graphs, Cycles of length 1 modulo 3 in graph, Approximation algorithms for channel assignment with constraints, The drawability problem for minimum weight triangulations, MacLane's planarity criterion for locally finite graphs, A new degree sum condition for the existence of a contractible edge in a \(\kappa\)-connected graph, On optimally-\(\lambda^{(3)}\) transitive graphs, Subpancyclicity of line graphs and degree sums along paths, Hamiltonicity in 3-connected claw-free graphs, Every 3-connected, essentially 11-connected line graph is Hamiltonian, Determinant of the distance matrix of a tree with matrix weights, Hamilton connectedness and the partially square graphs, A contribution to queens graphs: a substitution method, Partition the vertices of a graph into one independent set and one acyclic set, A survey on labeling graphs with a condition at distance two, Super edge-magic strength of fire crackers, banana trees and unicyclic graphs, A recursively construction scheme for super fault-tolerant Hamiltonian graphs, Some basic properties of multiple Hamiltonian covers, Collapsible biclaw-free graphs, Total chromatic number of one kind of join graphs, Conditional colorings of graphs, Path extendability of claw-free graphs, On the length of longest alternating paths for multicoloured point sets in convex position, Power domination in graphs, Power domination in block graphs, Minimal invariant sets in a vertex-weighted graph, Graph colourings and solutions of systems of equations over finite fields, On the number of 4-contractible edges in 4-connected graphs, Edge vulnerability parameters of bisplit graphs, On the restricted forwarding index problem in communication networks, The flow and tension spaces and lattices of signed graphs, Characterizing defect \(n\)-extendable graphs and \((2n+1)\)-critical graphs, Transformation graph \(G^{-+-}\), Steiner centers and Steiner medians of graphs, Every 4-connected line graph of a quasi claw-free graph is Hamiltonian connected, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, On minimal cost-reliability ratio spanning trees and related problems, A generalization of Dirac's theorem: subdivisions of wheels, A note on doubly stochastic graph matrices, A characterization of pancyclic complements of line graphs, Some degree bounds for the circumference of graphs, On flows in bidirected graphs, The number of spanning trees of plane graphs with reflective symmetry, Eigenvectors and eigenvalues of non-regular graphs, 6-path-connectivity and 6-generation, Maximum genus, connectivity and minimal degree of graphs, Cycle embedding in star graphs with edge faults, The globally bi-\(3^*\) and hyper bi-\(3^*\) connectedness of the spider web networks, Knots and links in spatial graphs: a survey, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Tabular graphs and chromatic sum, The competition number of a graph having exactly one hole, Edge cuts leaving components of order at least \(m\), Balanced star decompositions of regular multigraphs and \(\lambda\)-fold complete bipartite graphs, Degree conditions for forests in graphs, A note about shortest cycle covers, Minimally circular-imperfect graphs with a major vertex, Small embeddings for partial cycle systems of odd length, Factor domination in graphs, The neighborhood union of independent sets and hamiltonicity of graphs, Reachability problems in edge-colored digraphs, Polynomial time algorithms for two classes of subgraph problem, Upper bounds and algorithms for parallel knock-out numbers, Completing incomplete commutative Latin squares with prescribed diagonals, Proof of a conjecture of Haeggkvist on cycles and independent edges, Hamiltonian paths in vertex-symmetric graphs of order 4p, Size Ramsey numbers involving stars, A lower-bound for the number of productions required for a certain class of languages, Graphical t-wise balanced designs, Existence of Dlambda-cycles and Dlambda-paths, Traveling salesman cycles are not always subgraphs of Voronoi duals, Connected Cayley graphs of semi-direct products of cyclic groups of prime order by Abelian groups are Hamiltonian, On linear-time algorithms for five-coloring planar graphs, On the complexity of recognizing a class of generalized networks, A note on the complexity of finding regular subgraphs, Reconnaissance des graphes de cordes, A successful algorithm for the undirected Hamiltonian path problem, A case of non-convergent dual changes in assignment problems, Packings by cliques and by finite families of graphs, On theories of Whitney and Tutte, The theorem on planar graphs, A Chvátal-Erdős condition for (1,1)-factors in digraphs, Monomial ideals and points in projective space, Some theorems of uniquely pancyclic graphs, Clique partitions of the cocktail party graph, System structure: stability and controllability, A sufficient condition for oriented graphs to be Hamiltonian, On k-optimum dipath partitions and partial k-colourings of acyclic digraphs, Lins-Mandel manifolds as branched coverings of \(S^ 3\), Bipartite regular graphs and shortness parameters, Compatible path-cycle-decompositions of plane graphs, On an extremal problem concerning the interval number of a graph, Counterexamples to Adám's conjecture on arc reversals in directed graphs, Counterexample to a conjecture on Hamilton cycles, Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory, The facility layout problem, A short proof and a strengthening of the Whitney 2-isomorphism theorem on graphs, Semi-independence number of a graph and the existence of Hamiltonian circuits, Path and cycle sub-Ramsey numbers and an edge-colouring conjecture, Combinatorial properties of boundary NLC graph languages, Strong shift equivalence and shear adjacency of nonnegative square integer matrices, System-level diagnosis: analysis of two new models, On a conjecture of Foulds and Robinson about deltahedra, Bipartite permutation graphs, Some parameters of graph and its complement, Hamilton cycles in directed Euler tour graphs, On computing a conditional edge-connectivity of a graph, Test schedules for VLSI circuits having built-in test hardware, The maximum number of cycles in the complement of a tree, Graph decomposition with constraints in the minimum degree, Bridged graphs and geodesic convexity, Extremal 3-connected graphs, On maximum cycle-distributed graphs, Tight bounds on the spectral radius of asymmetric nonnegative matrices, An application of discrete mathematics in the design of an open pit mine, Mininal linear spaces, Embedding partial triple systems, Variations on the Gallai-Milgram theorem, Embedding partial Mendelsohn triple systems, A randomised 3-colouring algorithm, A ternary search problem on graphs, On computing graph closures, Theoretical forms of n-point galaxy correlation functions, On the unit interval number of a graph, Steiner triple systems with an involution, A note on Nagami's polynomial invariants for graphs, On the Penrose number of cubic diagrams, Elementary proofs of (relatively) recent characterizations of Eulerian graphs, Spanning Eulerian subgraphs and matchings, Some inequalities about connected domination number, The reduction of graph families closed under contraction, Graphs without spanning closed trails, On the number of edge-disjoint one factors and the existence of \(k\)-factors in complete multipartite graphs, Partition of a directed bipartite graph into two directed cycles, Maximal and minimal vertex-critical graphs of diameter two, Source sink flows with capacity installation in batches, On diameter critical graphs, An algorithm for imbedding cubic graphs in the torus, Edge orientations on cubic graphs with a maximum number of pairs of oppositely oriented edges, Ramsey numbers for matchings, Non-Hamiltonian simple 3-polytopes having just two types of faces, Implicit data structures for fast search and update, On \(O(n^2)\) heuristic algorithm for the directed Steiner minimal tree problem, Minimum graphs with complete k-closure, Regular separable graphs of minimum order with given diameter, On a Diophantine equation arising in graph theory, Complexity of graph embeddability problems, On Harrington's partition relation, Complement reducible graphs, Optimal assignment of broadcasting frequencies, Concerning the complexity of deciding isomorphism of block designs, On k-path Hamiltonian maximal planar graphs, Permutation-operator inequalities on certain symmetry classes of tensors, Disjoint cliques and disjoint maximal independent sets of vertices in graphs, Some asymptotic ith Ramsey numbers, Strongly regular graphs and finite Ramsey theory, Hamiltonian paths in vertex-symmetric graphs of order 5p, Existence of dominating cycles and paths, On the properties of arbitrary hypercubes, The embedding of partial triple systems when 4 divides \(\lambda\), More powerful closure operations on graphs, A necessary and sufficient condition for a graph \(G\) with diameter 5 to be 2-diameter-stable, The chromatic index of multigraphs of order at most 10, Long dominating cycles in graphs, Antipodal covers of strongly regular graphs, Orienting cycle elements in orientable rotation systems, Characterising the linear complexity of span 1 de Bruijn sequences over finite fields., Nested chain partitions of Hamiltonian filters, Harper-type lower bounds and the bandwidths of the compositions of graphs, Minimum matrix representation of Sperner systems, A fast parallel algorithm to recognize P4-sparse graphs, Edge-foreward index of star graphs and other Cayley graphs, The exponent of the primitive Cayley digraphs on finite abelian groups, Hamiltonicity in 2-connected graphs with claws, A strongly polynomial algorithm for the inverse shortest arborescence problem, Intersections of longest cycles in \(k\)-connected graphs, Covering the edges of a graph by a prescribed tree with minimum overlap, The rectangle of influence drawability problem, Kronecker product graph matching., A time-optimal solution for the path cover problem on cographs., \(M\)-alternating paths in \(n\)-extendable bipartite graphs, Small cycle cover of 2-connected cubic graphs, Blocking nonorientability of a surface, The chromatic number of a graph of girth 5 on a fixed surface, Closure and forbidden pairs for Hamiltonicity, Graphs with fourth Laplacian eigenvalue less than two, Edge-disjoint trees containing some given vertices in a graph, Planar \(k\)-cycle resonant graphs with \(k=1,2\), Super-connectivity and super-edge-connectivity for some interconnection networks, The complexity of the locally connected spanning tree problem, Maximum genus and chromatic number of graphs, A note on the bounded fragmentation property and its applications in network reliability, A note on limit points for algebraic connectivity, On spectral integral variations of mixed graphs, Graphs whose positive semi-definite matrices have nullity at most two, Two sharp upper bounds for the Laplacian eigenvalues., Matrices with totally signed powers., Covers of Eulerian graphs, Circular chromatic number and a generalization of the construction of Mycielski., Sharp upper bounds on the spectral radius of graphs, When a zero-divisor graph is planar or a complete \(r\)-partite graph, On the identification problems in products of cycles, A result on Vizing's conjecture, The chromatic uniqueness of certain complete \(t\)-partite graphs., On some super fault-tolerant Hamiltonian graphs, The maximum deviation just-in-time scheduling problem., Connectivity of \(k\)-extendable graphs with large \(k\)., Expanding and forwarding parameters of product graphs, Tree-width, clique-minors, and eigenvalues., On maximum number of edges in a spanning eulerian subgraph, Number of maximum matchings of bipartite graphs with positive surplus, Cycles through given vertices and closures, Coloring planar Toeplitz graphs and the stable set polytope., Bipartite graphs with small third Laplacian eigenvalue., Some properties of Ramsey numbers, The energy of a graph, From Hall's matching theorem to optimal routing on hypercubes, Short solution of Kotzig's problem for bipartite graphs, On the edge connectivity, Hamiltonicity, and toughness of vertex-transitive graphs, Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian, Three-dimensional orthogonal graph drawing algorithms, Container ship stowage problem complexity and connection to the coloring of circle graphs, Spring algorithms and symmetry, The \(m\)-step competition graph of a digraph, Coloring graphs with no \(\text{odd-}K_4\), Closure concepts for claw-free graphs, Hamilton cycles in tensor product of graphs, Extremal graphs in some coloring problems, A structure theorem for pseudomanifolds, On endo-homology of complexes of graphs, Edge degree conditions for subpancyclicity in line graphs, Cycle factorizations of cycle products, Tree-visibility orders, On a problem concerning ordered colourings, On cubic polyhedral graphs with prescribed adjacency properties of their faces, Minimal \(2\)-connected non-Hamiltonian claw-free graphs, 2-factors and Hamiltonicity, On the clique-transversal number of chordal graphs, Tree-like \(P_4\)-connected graphs, Neighborhood conditions for graphs with induced claws, Note on alternating directed cycles, Subgraphs with restricted degrees of their vertices in planar graphs, Stallings foldings and subgroups of free groups, On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\), On vertex ranking of a starlike graph, A necessary condition for a graph to be the visibility graph of a simple polygon, A note on minimum degree conditions for supereulerian graphs, On Wiener numbers of polygonal nets, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Embeddings of \(k\)-connected graphs of pathwidth \(k\), A new degree condition for graphs to have \([a,b\)-factor], Eulerian subgraphs and Hamilton-connected line graphs, Double covers of cubic graphs with oddness 4, The partition of a strong tournament, Characterizations of maximum matching graphs of certain types, The Kauffman brackets for equivalence classes of links, The 3-choosability of plane graphs of girth 4, 4-regular claw-free IM-extendable graphs, Information loss in three cell-level control techniques for summary tables, Support sizes of sixfold triple systems, On \(\sigma\)-polynomials and a class of chromatically unique graphs, \(p\)-competition graphs, Chromatic numbers of competition graphs, On the problem of consistent marking of a graph, Expanding and forwarding, A note on the total chromatic number of Halin graphs with maximum degree 4, Two conjectures on uniquely totally colorable graphs, Some problems on factorizations with constraints in bipartite graphs, The CW-inequalities for vectors in \(\ell_ 1\), Toughness of graphs and the existence of factors, The exponent set of symmetric primitive (0,1) matrices with zero trace, Fixed edge-length graph drawing is NP-hard, Solution of a delta-system decomposition problem, Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs, The subchromatic number of a graph, Toughness and matching extension in graphs, The smallest eigenvalue for reversible Markov chains, The largest eigenvalue of nonregular graphs, On the two conjectures of Graffiti, On the minor-minimal 2-connected graphs having a fixed minor, Graphs with no \(M\)-alternating path between two vertices, On the minimum real roots of the \(\sigma\)-polynomials and chromatic uniqueness of graphs, \(K_{p,q}\)-factorization of the complete bipartite graph \(K_{m,n}\), Neighborhood unions and cyclability of graphs, On the complexity of the approximation of nonplanarity parameters for cubic graphs, On the chromatic forcing number of a random graph, New upper and lower bounds for Ramsey numbers, Hereditarily hard \(H\)-colouring problems, On the bandwidth of triangulated triangles, Storage efficient decoding for a class of binary de Bruijn sequences, On the independence number in \(K_{1,r+1}\)-free graphs, Pancyclicity of hamiltonian line graphs, A generalized class-teacher model for some timetabling problems, Chromatic roots and Hamiltonian paths, Which crossing number is it anyway?, Face size and the maximum genus of a graph. I: Simple graphs, A sharp upper bound of the spectral radius of graphs, Line graphs and forbidden induced subgraphs, Long cycles through a linear forest, A degree sum condition for the existence of a contractible edge in a \(\kappa\)-connected graph, Covering non-uniform hypergraphs, On structure of some plane graphs with application to choosability, All 4-connected line graphs of claw free graphs are Hamiltonian connected, Flexibility of polyhedral embeddings of graphs in surfaces, Partitioning vertices of a tournament into independent cycles, Decomposing a planar graph into an independent set and a 3-degenerate graph, Almost all 3-connected graphs contain a contractible set of \(k\) vertices, Subgraph coverings and edge switchings, Odd wheels in graphs, Polynomials associated with nowhere-zero flows, Graphs with magnetic Schrödinger operators of low corank, Products of circulant graphs are metacirculant., On a conjecture of Woodall, Fault-tolerant Hamiltonian laceability of hypercubes., Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application., Ring embedding in faulty honeycomb rectangular torus., Finding approximate palindromes in strings, Theory of 2-3 heaps, Determination of the star valency of a graph, On embedding an outer-planar graph in a point set, Efficient visibility queries in simple polygons, On the Laplacian spectrum of (\(\alpha,\omega\))-graphs, Cycle cover ratio of regular matroids, The characterization of symmetric primitive matrices with exponent \(n-1\)., Towards area requirements for drawing hierarchically planar graphs, Complete-factors and (\(g,f\))-factors, Hamiltonicity of 3-connected quasi-claw-free graphs., The Hamiltonian index of a graph and its branch-bonds, \(\sigma\)-polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, The number of removable edges in a 4-connected graph, Three-coloring Klein bottle graphs of girth five, New sufficient conditions for bipancyclic bipartite graphs, Hamiltonian decompositions of prisms over cubic graphs, Mixed hypercacti, Cycle lengths and chromatic number of graphs, Rainbow numbers for matchings and complete graphs, Minor-minimal 6-regular graphs in the Klein bottle, Generating cycle spaces for graphs on surfaces with small genera, On \(k\)-pairable graphs, Removable edges in a cycle of a 4-connected graph, Characterizing \(2k\)-critical graphs and \(n\)-extendable graphs, Distributive online channel assignment for hexagonal cellular networks with constraints, Minimizing maximum indegree, Upon the removal of the edges of a 1-factor from an even circuit in a 2-connected graph, A note on biased and non-biased games, Generalized perfect graphs: Characterizations and inversion, Long cycles in graphs with prescribed toughness and minimum degree, Vertex arboricity and maximum degree, Neighborhood unions and hamiltonicity of graphs, Ordered colourings, A Hamiltonian game on \(K_{n,n}\), Minimal graphs that fold onto \(K_ n\), Linear time optimization algorithms for \(P_ 4\)-sparse graphs, Large survivable nets and the generalized prisms, Planar graphs with few vertices of small degree, Strength and fractional arboricity of complementary graphs, Orthogonal \((g,f)\)-factorizations in graphs, Hamilton cycles and eigenvalues of graphs, Every matroid is a submatroid of a uniformly dense matroid, An optimal path cover algorithm for cographs, Dominating cycles in bipartite biclaw-free graphs, Supereulerian graphs and excluded induced minors, Circumferences in 1-tough graphs, Nonabelian sets with distinct \(k\)-sums, On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope, Intelligent transportation systems -- Enabling technologies, A computational attack on the conjectures of Graffiti: New counterexamples and proofs, On the colorings of outerplanar graphs, Trees with the same degree sequence and path numbers, A new bound on the feedback vertex sets in cubic graphs, The 2-extendability of strongly regular graphs, Long cycles in bipartite tournaments, Planar graphs on the projective plane, Least domination in a graph, Toughness, hamiltonicity and split graphs, The cordiality of the path-union of \(n\) copies of a graph, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, Laplacian spectra and spanning trees of threshold graphs, Graphs that admit 3-to-1 or 2-to-1 maps onto the circle, The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs, On the structure of trapezoid graphs, The Chvátal-Erdös condition for cycles in triangle-free graphs, On the fixed edge of planar graphs with minimum degree five, The number of complements of a topology on \(n\) points is at least \(2^ n\) (except for some special cases), Nowhere-zero 4-flows and cycle double covers, A tight lower bound for optimal bin packing, On the minimum Perron value for an irreducible tournament matrix, Decompositions of regular graphs into \(K^ c_ n \vee 2K_ 2\), An application of matching theory of edge-colourings, The complexity of generalized graph colorings, Optimal path cover problem on block graphs, Linear estimation in models based on a graph, A tree whose complement is not eigensharp, On the computational complexity of edge concentration, The basic algorithm for pseudo-Boolean programming revisited, Extreme chordal doubly nonnegative matrices with given row sums, Finding a complete matching with the maximum product on weighted bipartite graphs, Regular factors in regular graphs, Recognizing a class of bicircular matroids, The Ramsey numbers of trees versus \(W_{6}\) or \(W_{7}\), Edge fault tolerance analysis of a class of interconnection networks, Construction of a family of graphs with a small induced proper subgraph with minimum degree 3, Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching, Edge vulnerability parameters of split graphs, Restricted connectivity for three families of interconnection networks, A census of boundary cubic rooted planar maps, An efficient condition for a graph to be Hamiltonian, Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes, The algorithmic complexity of the minus clique-transversal problem, A bound on 4-restricted edge connectivity of graphs, On the vertex arboricity of planar graphs of diameter two, Node-disjoint paths in hierarchical hypercube networks, The Wiener index of the \(k\)th power of a graph, Hamilton cycles in circuit graphs of matroids, Generalized Latin squares and their defining sets, A degree sum condition for long cycles passing through a linear forest, Hamiltonian connected hourglass free line graphs, Locally constrained graph homomorphisms and equitable partitions, On an adjacency property of almost all tournaments, Berge's conjecture on directed path partitions -- a survey, Which claw-free graphs are strongly perfect?, On commutativity of two unary digraph operations: subdividing and line-digraphing, On the 2-factor index of a graph, On the complexity of dominating set problems related to the minimum all-ones problem, Corrections of proofs for Hansen and Mélot's two theorems, Ordering trees with algebraic connectivity and diameter, Minimum cycle bases of graphs on surfaces, Sufficient conditions for restricted-edge-connectivity to be optimal, Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, The structure of \(K_{3,3}\)-subdivision-free toroidal graphs, Hybrid one-dimensional reversible cellular automata are regular, On the number of contractible triples in 3-connected graphs, The base sets of primitive zero-symmetric sign pattern matrices, On spanning connected graphs, Equitable coloring planar graphs with large girth, Some graphs of class 1 for \(f\)-colorings, Panconnectivity and edge-pancyclicity of faulty recursive circulant \(G(2^m,4)\), An upper bound on the independence number of benzenoid systems, On conditional diagnosability of the folded hypercubes, Removable edges in a 5-connected graph and a construction method of 5-connected graphs, Toughness and the existence of fractional \(k\)-factors of graphs, The diameter of the acyclic Birkhoff polytope, On the spectral radius of graphs with a given domination number, A graphical construction of the D-optimal saturated, \(3\times s^{2}\) main effect, factorial design, Energy conservation in wireless sensor networks and connectivity of graphs, The computational complexity of the parallel knock-out problem, On the hardness of optimization in power-law graphs, Hyper-Hamiltonian generalized Petersen graphs, Distance domination-critical graphs, Characterization of graphs with infinite cyclic edge connectivity, All 2-connected in-tournaments that are cycle complementary, Characterizing minimally \(n\)-extendable bipartite graphs, Connected even factors in claw-free graphs, Graph \(Z_{n}\) and some graphs related to \(Z_{n}\) are determined by their spectrum, Doubly stochastic matrices of trees, Chromatic sums of 2-edge-connected maps on the plane, Extension of a list coloring problem, On mutually independent Hamiltonian paths, Bounds for the b-chromatic number of some families of graphs, Semi-hyper-connected edge transitive graphs, A better heuristic for area-compaction of orthogonal representations