On edges crossing few other edges in simple topological complete graphs

We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².     

Regular subgraphs of dense graphs

Every graph onn vertices, with at leastc _k n logn edges contains ak-regular subgraph. This answers a question of Erdős and Sauer.     

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log₂ n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n ²/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday     

Enumeration of simple complete topological graphs

A simple topological graph T=(V(T),E(T)) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2^Θ(n4). We also show that the number of weak isomorphism classes of simple complete topological graphs with n vertices and crossings is at least 2^{n(logn−O(1))}, which improves the estimate of Harborth and Mengersen.     

Supereulerian complementary graphs

Nebeský in [12] show that for any simple graph with n ≥ 5 vertices, either G or G^c contains an eulerian subgraph with order at least n - 1, with an explicitly described class of exceptional graphs. In this note, we show that if G is a simple graph with n ≥ 61 vertices, then either G or G^c is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G^c are connected, then either G or G^c has a 4-flow, or both G and G^c have cut-edges. © 1993 John Wiley & Sons, Inc.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

On connection between the switching separability of a graph and its subgraphs

A graph of order n ≥ 4 is called switching separable if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent subgraphs, each having at least two vertices. We prove the following: If removing any one or two vertices of a graph always results in a switching separable subgraph then the graph itself is switching separable. On the other hand, for each odd order greater than 4, there is a graph that is not switching separable, but removing a vertex always results in a switching separable subgraph. We show some connection with similar facts on the separability of Boolean functions and the reducibility of n-ary quasigroups.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement

Erd?s and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^?(H) for some ?(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Recognizing String Graphs Is Decidable

Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.     

Recognizing String Graphs Is Decidable

   Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

A Turán type problem for interval graphs

We consider the following analogue of a problem of Turán for interval graphs: Let c = c(n, m) be the largest integer such that any interval graph with n vertices and at least m edges contains a complete subgraph on c vertices. We determine the value of c(n, m) explicitly.     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) time a planar embedding of G, where vertex v _i is represented by point p _i and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

A fast algorithm for equitable coloring

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn ²) time, where n is the number of vertices.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

On two problems in graph Ramsey theory

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K _N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 ^cΔlogΔ . The induced Ramsey number r _ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r _ind (H) ≤ 2 ^cnlogn . We move a step closer to proving this conjecture, showing that r _ind (H) ≤ 2 ^cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.