Search

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In this paper we investigate the related problem MinMovedVertices which asks for the minimum number of vertex moves. First, we show that MinMovedVertices is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BendPointSetEmbeddability, which yields similar results for that problem. Third, we give bounds for the behavior of MinMovedVertices on trees and general planar graphs. [ABSTRACT FROM AUTHOR]

The so called (σ,ρ)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (σ,ρ)-dominating if for every vertex v ∈ S, S ∩ N(v) ∈ σ, and for every v ∉ S, S ∩ N(v) ∈ ρ, where σ and ρ are sets of nonnegative integers and N(v) denotes the open neighborhood of the vertex v in G.) It was known that for any two nonempty finite sets σ and ρ (such that 0 ∉ ρ), the decision problem whether an input graph contains a (σ,ρ)-dominating set is NP-complete, but that when restricted to chordal graphs, some polynomial time solvable instances occur. We show that for chordal graphs, the problem performs a complete dichotomy: it is polynomial time solvable if σ, ρ are such that every chordal graph contains at most one (σ,ρ)-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs (σ,ρ) by a structural description, but at least we can provide a recursive algorithm for their recognition. If ρ contains the 0 element, every graph contains a (σ,ρ)-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-(σ,ρ)-domination problem is NP-complete for chordal graphs whenever ρ contains, besides 0, at least one more integer. [ABSTRACT FROM AUTHOR]

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G = (V,E) into an interval of integers [0..k] is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k ≥ 4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O((k + 1)n) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k = 4 - here the running time of our algorithm is O(1.3161n). [ABSTRACT FROM AUTHOR]

Geometric intersection graphs are intensively studied both for their practical motivation and interesting theoretical properties. Many such classes are hard to recognize. We ask the question if imposing restrictions on the girth (the length of a shortest cycle) of the input graphs may help in finding polynomial time recognition algorithms. We give examples in both directions. First we present a polynomial time recognition algorithm for intersection graphs of polygons inscribed in a circle for inputs of girth greater than four (the general recognition problem is NP-complete). On the other hand, we prove that recognition of intersection graphs of segments in the plane remains NP-hard for graphs with arbitrarily large girth. [ABSTRACT FROM AUTHOR]

We prove that in the List version, the problem of deciding the existence of a locally injective homomorphism to a parameter graph H performs a full dichotomy. Namely we show that it is polynomially time solvable if every connected component of H has at most one cycle and NP-complete otherwise. [ABSTRACT FROM AUTHOR]

We present a fixed parameter tractable algorithm for the Independent Set problem in 2-dir graphs and also its generalization to d-dir graphs. A graph belongs to the class of d-dir graphs if it is an intersection graph of segments in at most d directions in the plane. Moreover our algorithms are robust in the sense that they do not need the actual representation of the input graph and they answer correctly even if they are given a graph from outside the promised class. [ABSTRACT FROM AUTHOR]

Regular maps are cellular decompositions of closed surfaces with the highest ‘level of symmetry', meaning that the automorphism group of the map acts regularly on flags. We survey the state-of-the-art of the problem of classification of regular maps on a given surface and outline directions of future research in this area. [ABSTRACT FROM AUTHOR]

It is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed cdn, where c is a constant. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices. [ABSTRACT FROM AUTHOR]

Szemerédi's regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the regularity method for graphs and has proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science. Recently, the graph regularity method was extended to hypergraphs by Gowers and by Skokan and the authors. The hypergraph regularity method has been successfully employed in a handful of combinatorial applications, including alternative proofs to well-known density theorems of Szemerédi and of Purstenberg and Katznel-son. In this paper, we apply the hypergraph regularity method to a few extremal hypergraph problems of Ramsey and Turán flavor. [ABSTRACT FROM AUTHOR]

Property-testers are fast randomized algorithms for distinguishing between graphs (and other combinatorial structures) satisfying a certain property, from those that are far from satisfying it. In many cases one can design property-testers whose running time is in fact independent of the size of the input. In this paper we survey some recent results on testing graph properties. A common thread in all the results surveyed is that they rely heavily on the simple yet useful notion of graph homomorphism. We mainly focus on the combinatorial aspects of property-testing. [ABSTRACT FROM AUTHOR]

For non-trivial Heyting algebras H1, H2 one always has at least one homomorphism H1 →H2; if H1 = H2 there is at least one non-identical one. A Heyting algebra H is almost rigid if ∣ End(H)∣ = 2 and a system of almost rigid algebras ℌ is said to be discrete if ∣ Hom(H1, H2)∣ = 1 for any two distinct H1, H2 ∈ ℌ. We show that there exists a discrete system of 2ω countable almost rigid Heyting algebras. [ABSTRACT FROM AUTHOR]

Let Q be a nonbipartite quadrangulation of the projective plane. Youngs [You96] proved that Q cannot be 3-colored. We prove that for every 4-coloring of Q and for any two colors a and b, the number of faces F of Q, on which all four colors appear and colors a and b are not adjacent on F, is odd. This strengthens previous results that have appeared in [You96, HRS02, Moh02, CT04]. If we form a triangulation of the projective plane by inserting a vertex of degree 4 in every face of Q, we obtain an Eulerian triangulation T of the projective plane whose chromatic number is 5. The above result shows that T is never 5-critical. We show that sometimes one can remove two, three, or four, vertices from T and obtain a 5-critical graph. This gives rise to an explicit construction of 5-critical graphs on the projective plane and yields the first explicit family of 5-critical graphs with arbitrarily large edge-width on a fixed surface. [ABSTRACT FROM AUTHOR]

We prove that the vertex set of any twin-free loopless multigraph G has an embedding into some point set P of some Euclidean space ℝk, such that the automorphism group of G is isomorphic to the isometry group of ℝk globally preserving P. [ABSTRACT FROM AUTHOR]

The study of circular chromatic number Xc(G) of a graph G, which is a refinement of its chromatic number, has been very active in the past decade. Many nice results are obtained, new techniques are developed, and connections to other fields are established. This paper presents a glimpse of the recent progress on this subject. Besides presenting the results, some of the ideas and tools in the proofs are explained, although no detailed proofs are contained. [ABSTRACT FROM AUTHOR]

We present a polynomial algorithm, implicit in the work of El-Zahar and Sauer, which inputs a 3-colouring of a categorical product of two graphs and outputs a 3-colouring of one of the factors. We raise a question about the existence of polynomial algorithms for colouring the vertices of some graphs in terms of intrinsic succint description of the vertices rather than in terms of the (exponential) size of the graph. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper acyclic coloring c of G such that c(v) ∈ L(v) for all v ∈ V. If G is acyclically L-list colorable for any list assignment with L(v) ≥ k for all v ∈ V, then G is acyclically k-choosable. Let G be a planar graph without 4-cycles and 5-cycles. In this paper, we prove that G is acyclically 4-choosable if G furthermore satisfies one of the following conditions: (1) without 6-cycles; (2) without 7-cycles; (3) without intersecting triangles. [ABSTRACT FROM AUTHOR]

We consider the problem of determining the minimum chromatic number of graphs and hypergraphs of large girth which cannot be mapped under a homomorphism to a specified graph or hypergraph. More generally, we are interested in large girth hypergraphs that do not admit a vertex partition of specified size such that the subhypergraphs induced by the partition blocks have a homomorphism to a given hypergraph. In the process, a general probabilistic construction of large girth hypergraphs is obtained, and general definitions of chromatic number and homomorphisms are considered. [ABSTRACT FROM AUTHOR]

A graph is path k-colorable if it has a vertex k-coloring in which the subgraph induced by each color class is a disjoint union of paths. A graph is path k-choosable if, whenever each vertex is assigned a list of k colors, such a coloring exists in which each vertex receives a color from its list. It is known that every planar graph is path 3-colorable [Poh90, God91] and, in fact, path 3-choosable [Har97]. We investigate which planar graphs are path 2-colorable or path 2-choosable. We seek results of a "threshold" nature: on one side of a threshold, every graph is path 2-choosable, and there is a fast coloring algorithm; on the other side, determining even path 2-colorability is NP-complete. We first consider maximum degree. We show that every planar graph with maximum degree at most 4 is path 2-choosable, while for k ≥ 5 it is NP-complete to determine whether a planar graph with maximum degree k is path 2-colorable. Next we consider girth. We show that every planar graph with girth at least 6 is path 2-choosable, while for k ≤ 4 it is NP-complete to determine whether a planar graph with girth k is path 2-colorable. The case of girth 5 remains open. [ABSTRACT FROM AUTHOR]

Graph colourings may be viewed as special constraint satisfaction problems. The class of k-colouring problems enjoys a well known dichotomy of complexity — these problems are polynomial time solvable when k ≤ 2, and NP-complete when k ≥ 3. For general constraint satisfaction problems such dichotomy was conjectured by Feder and Vardi, but has still not been proved in full generality. We discuss some results and techniques related to this Dichotomy Conjecture. We focus on the effects of a new concept of ‘fullness', and how it affects the complexity of constraint satisfaction problems and their dichotomy. Full constraint satisfaction problems may then be specialized back to graph colourings, yielding an interesting novel class of problems in graph theory, related to the study of graph perfection. [ABSTRACT FROM AUTHOR]

We study the fixed parameter tractability of the restrictive H-coloring and the restrictive list H-coloring problems, introduced in [DST01]. The parameter-izations are defined by fixing the number of pre-images of a subset C of the vertices in H through a partial weight assignment (C, K). We define two families of partially weighted graphs: the simple and the plain. For the class of simple partially weighted graphs, we show the fixed parameter tractability of the list (H, C, K)-coloring problem. For the more general class of plain partially weighted graphs, we prove the fixed parameter tractability of the (H, C, K)-coloring problem. [ABSTRACT FROM AUTHOR]

Counting homomorphisms between graphs (often with weights) comes up in a wide variety of areas, including extremal graph theory, properties of graph products, partition functions in statistical physics and property testing of large graphs. In this paper we survey recent developments in the study of homomorphism numbers, including the characterization of the homomorphism numbers in terms of the semidefiniteness of "connection matrices", and some applications of this fact in extremal graph theory. We define a distance of two graphs in terms of similarity of their global structure, which also reflects the closeness of (appropriately scaled) homomorphism numbers into the two graphs. We use homomorphism numbers to define convergence of a sequence of graphs, and show that a graph sequence is convergent if and only if it is Cauchy in this distance. Every convergent graph sequence has a limit in the form of a symmetric measurable function in two variables. We use these notions of distance and graph limits to give a general theory for parameter testing. The convergence can also be characterized in terms of mappings of the graphs into fixed small graphs, which is strongly connected to important parameters like ground state energy in statistical physics, and to weighted maximum cut problems in computer science. [ABSTRACT FROM AUTHOR]

We study various properties of a random graph Rn, drawn uniformly at random from the class $$ \mathcal{A}_n $$ of all simple graphs on n labelled vertices that satisfy some given property, such as being planar or having tree-width at most κ. In particular, we show that if the class $$ \mathcal{A} $$ is' small' and ‘addable', then the probability that Rn is connected is bounded away from 0 and from 1. As well as connectivity we study the appearances of subgraphs, and thus also vertex degrees and the numbers of automorphisms. We see further that if $$ \mathcal{A} $$ is' smooth' then we can make much more precise statements for example concerning connectivity. [ABSTRACT FROM AUTHOR]

We show that any cubic bridgeless graph with m edges contains two perfect matchings that cover at least 3m/5 edges, and three perfect matchings that cover at least 27m/35 edges. [ABSTRACT FROM AUTHOR]

Our aim is to exhibit a short algebraic proof for the Erdös-Ko-Rado theorem. First, we summarize the method of linearly independent polynomials showing that if X1,..., Xm ⊂ [n] are sets such that Xi does not satisfy any of the set of s intersection conditions Ri but Xi satisfies at least one condition in Rj for all j > i then $$ m \leqslant \left( {\begin{array}{*{20}c} n \\ s \\ \end{array} } \right) + \left( {\begin{array}{*{20}c} n \\ {s - 1} \\ \end{array} } \right) + \cdot \cdot \cdot + \left( {\begin{array}{*{20}c} n \\ 0 \\ \end{array} } \right) $$. The EKR theorem is follows by carefully choosing the intersection properties and adding extra polynomials. We also prove generalizations for non-uniform families with various intersection conditions. [ABSTRACT FROM AUTHOR]

An ordered graph is a graph together with a linear order on its vertices. A hereditary property of ordered graphs is a collection of ordered graphs closed under taking order-preserving isomorphisms of the vertex set, and order-preserving induced subgraphs. If P is a hereditary property of ordered graphs, then Pn denotes the collection $$ \left\{ {G \in \mathcal{P}:V(G) = [n]} \right\} $$, and the function $$ n \mapsto \left {\mathcal{P}_n } \right $$ is called the speed of P. The possible speeds of a hereditary property of labelled graphs have been extensively studied (see [BBW00] and [Bol98] for example), and more recently hereditary properties of other combinatorial structures, such as oriented graphs ([AS00], [BBM06+c]), posets ([BBM06+a], [BGP99]), words ([BB05], [QZ04]) and permutations ([KK03], [MT04]), have also attracted attention. Properties of ordered graphs generalize properties of both labelled graphs and permutations. In this paper we determine the possible speeds of a hereditary property of ordered graphs, up to the speed 2n−1. In particular, we prove that there exists a jump from polynomial speed to speed Fn, the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from p(n)Fn,k to Fn,k+1 (where p(n) is a polynomial and Fn,k are the generalized Fibonacci numbers) converging to 2n−1. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations. [ABSTRACT FROM AUTHOR]

We give an explicit construction of a three-coloring of KN,N in which no Kr,r is monochromatic for r = N1/2−ε, where ε > 0 is a constant. [ABSTRACT FROM AUTHOR]

The induced Ramsey number IR(G, H) is the least positive integer N such that there exists an N-vertex graph F with the property that for each 2-coloring of its edges with red and blue, either some induced in F subgraph isomorphic to G has all its edges colored red, or some induced in F subgraph isomorphic to H has all its edges colored blue. In this paper, we study IR(P3, H) for various H, where P3 is the path with 3 vertices. In particular, we answer a question by Gorgol and Luczak by constructing a family {Hnn=1∞ such that $$ \mathop {lim}\limits_{n \to \infty } \sup \tfrac{{IR(P_3 ,H_n )}} {{IR_w (P_3 ,H_n )}} > 1 $$, where IRw(G, H) is defined almost as IR(G,H), with the only difference that G should be induced only in the red subgraph of F (not in F itself) and H should be induced only in the blue subgraph of F. [ABSTRACT FROM AUTHOR]

The systems of linear equations (homogeneous or inhomogeneous) that are partition regular, over ℕ or ℤ or ℚ, were characterized by Rado. Our aim here is to characterize those systems for which we can guarantee a nonconstant, or injective, solution. It turns out that we thereby recover an equivalence between ℕ and ℤ that is normally lost when one passes from homogeneous to inhomogeneous systems. [ABSTRACT FROM AUTHOR]

Assume that the edges of a complete bipartite graph K(A, B) are colored with r colors. In this paper we study coverings of B by vertex disjoint monochromatic cycles, connected matchings, and connected subgraphs. These problems occur in several applications. [ABSTRACT FROM AUTHOR]

For any coloring of the N × N grid using fewer than log log N colors, one can always find a monochromatic equilateral right triangle, a triangle with vertex coordinates (x, y), (x + d, y), and (x,y + d). [ABSTRACT FROM AUTHOR]

The F-triangle is a refined face count for the generalised cluster complex of Fomin and Reading. We compute the F-triangle explicitly for all irreducible finite root systems. Furthermore, we use these results to partially prove the "F = M Conjecture" of Armstrong which predicts a surprising relation between the F-triangle and the Möbius function of his m-divisible partition poset associated to a finite root system. [ABSTRACT FROM AUTHOR]

A quasivariety ℚ is Q-universal if, for any quasivariety $$ \mathbb{V} $$ of algebraic systems of a finite similarity type, the lattice L($$ \mathbb{V} $$) of all subquasivarieties of $$ \mathbb{V} $$ is isomorphic to a quotient lattice of a sublattice of the lattice L(ℚ) of all subquasivarieties of ℚ. We investigate Q-universality of finitely generated varieties of distributive double p-algebras. In an earlier paper, we proved that any finitely generated variety of distributive double p-algebras categorically universal modulo a group is also Q-universa1. Here we consider the remaining finitely generated varieties of distributive double p-algebras and state a problem whose solution would complete the description of all Q-universal finitely generated varieties of distributive double p-algebras. [ABSTRACT FROM AUTHOR]

Best possible estimates for the lengths of a Hamiltonian path and of a Hamiltonian polygon on a Euclidean simplex of given volume are given. The extreme cases are described. [ABSTRACT FROM AUTHOR]

We define an analogue of the the concept of J. H. Conway's number games for games of multiple players. We define the value of such number game as an element of a vector space over the Conway field. We interpret the value in terms of the strategy of the game, and prove that all possible values in the vector space can occur. [ABSTRACT FROM AUTHOR]

We use ergodic-theoretical tools to study various notions of "large" sets of integers which naturally arise in theory of almost periodic functions, combinatorial number theory, and dynamics. Call a subset of N a Bohr set if it corresponds to an open subset in the Bohr compactification, and a piecewise Bohr set (PWB) if it contains arbitrarily large intervals of a fixed Bohr set. For example, we link the notion of PWB-sets to sets of the form A+B, where A and B are sets of integers having positive upper Banach density and obtain the following sharpening of a recent result of Renling Jin. Theorem. If A and B are sets of integers having positive upper Banach density, the sum set A+B is PWB-set. [ABSTRACT FROM AUTHOR]

We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl[1]. They proved that the problem is solvable in polynomial time for graphs with maximum degree three, but -hard for graphs with maximum degree six. One of our main results is closing the gap in these results, by proving -hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains -hard for planar graphs with maximum degree six and for 5-regular graphs. On the other hand we present a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an ‘almost balanced' ordering. [ABSTRACT FROM AUTHOR]

We prove that the L(2,1)-labeling problem is NP-complete for graphs of treewidth two, thus adding a natural and well studied problem to the short list of problems whose computational complexity separates treewidth one from treewidth two. We prove similar results for other variants of the distance constrained graph labeling problem. [ABSTRACT FROM AUTHOR]

An L(2,1)-labeling of a graph of span t is an assignment of integer labels from {0,1,...,t} to its vertices such that the labels of adjacent vertices differ by at least two, while vertices at distance two are assigned distinct labels. We show that for all k ≥ 3, the decision problem whether a k-regular graph admits an L(2,1)-labeling of span k+2 is -complete. This answers an open problem of R. Laskar. [ABSTRACT FROM AUTHOR]

A ranking of a graph is a coloring of the vertex set with positive integers such that on every path connecting two vertices of the same color there is a vertex of larger color. We consider the directed variant of this problem, where the above condition is imposed only on those paths in which all edges are oriented in the same direction. We show that the ranking number of a directed tree is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time. Unlike the undirected case, however, deciding whether the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard. [ABSTRACT FROM AUTHOR]