Search

Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width. An MSO property with edge quantifications (called an MSO2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation.

Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.

We consider a binary operation • on the set of triads ( G , A , B ) , where G is a graph and ( A , B ) is the partition of the set of the set V ( G ) . The operation • of multiplication of a triad and a graph is defined and the properties of the introduced operations are described. We study in detail the subcase, when the triads have the form ( G , A , B ) , where G is a bipartite graph and ( A , B ) is its bipartition. For this case the decomposition theorem stating that any graph except the described family of exceptions can be uniquely decomposed into indecomposable components with respect to the operation • is proved. Using this theorem, we proved the following. Let the graph G have a module M with associated partition ( A , B , M ) , where A ∼ M and B ≁ M , such that G [ A ∪ B ] is a bipartite graph with bipartition ( A , B ) . Then the graph G is reconstructible.

We consider the problem of partitioning a graph into k independent sets and l cliques, known as the ( k , l ) -partition problem, which was introduced by Brandstadt in [A. Bransdstadt, Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47–54], and generalized by Feder et al. in [T. Feder, P. Hell, S. Klein, and R. Motwani, Complexity of graph partition problems, in: Thirty First Annual ACM Symposium on Theory of Computing (1999), Plenum Press, New York, 1999, 464–472] as the M-partition problem. Brandstadt proved that given a graph G, it is NP-complete to decide if G is a ( k , l ) -graph for k ≥ 3 or l ≥ 3 . Since then, a lot of work have been done in order to solve the ( k , l ) -partition problem for many subclasses of perfect graphs. In this work, we consider a subclass of perfect graphs: the cographs, which correspond to graphs without paths with size 4. More precisely, we provide a characterization of cographs that are ( k , l ) -graphs by forbidden configurations, that is, a cograph G is a ( k , l ) -graph if and only if it does not contain any of the forbbiden configurations.

Search games are a powerfull tool for studying various connectivity parameters of graphs. In the classical search game, we consider an undirected graph G = (V, E) whose edges are initially contaminated. A set of searchers try to clean the graph. At the beginning the graph contains no searchers. At each step of the game, a searcher can be placed on an arbitrary vertex of the graph or, if the searcher is already on a vertex v it can slide through an edge e incident to v. In the former case the edge e is cleaned by the searcher. If, for some clean edge e, there is a path from e to a contaminated edge such that no searcher separates the two edges on the path, then e becomes recontaminated. The search number s(G) of G is the minimum number of searchers required to clean all the edges of G. The search number differs by at most one from another well-known graph parameter, namely the pathwidth. The treewidth, the branchwidth and several parameters of the same flavour can be defined by versions of the search game. In this paper we consider a variant of the search game introduced by Barriere et al. [1], called connected search. It requires that, at each step of the search game

We prove that the split decomposition of a graph is definable by Monadic Second-Order formulas. We also prove that the set of graphs having the same cycle matroid as a given graph is definable from this graph by Monadic Second-Order formulas. These results are consequences of general results on the logical definability of graph decompositions of various types.

In this paper we describe an algorithmic construction that, given a tree-decomposition of a graph G and a path-decomposition of a graph H , provides a tree-decomposition of the cartesian product of G and H . From the latter, we derive upper bounds on the treewidth and on the pathwidth of the cartesian product, expressed in terms of the treewidth and of the pathwidth of the two involved graphs. On the other hand, in the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and if the graphs in the finite set are all connected, the property of being an MS -definable set is also preserved.

Extremal graph theory, Ramsey theory and the theory of Random graphs are strongly connected to each other. Starting from these fields, we formulate some problems and results which are related to different levels of randomness. The first one is completely non-random, being the ordinary Ramsey-Turan problem and in the subsequent three problems we formulate some randomized variations of the problem. Speaking of graph properties, we shall consider them as sets of graphs and occasionally write G ∈ P instead of writing that G has property P. A graph property P is called monotone if adding an edge to a H n ∈ P, we get an H ∗ n ∈ P. We shall use three models of random graphs: the binomial, the hypergeometric and the stopping-rule model. This abstract contains the most important definitions.

This paper investigates a simple, constructive search strategy: an incomplete version of Ginsberg's Dynamic Backtracking which records no information during search, and randomly selects variables for backtracking. Combining this with forward checking and dynamic variable ordering heuristics we obtain algorithms for constraint satisfaction problems, and by adding branch-and-bound we obtain optimization algorithms. Testing these on several classes of 1000-vertex graph colouring problems we find colourings which are competitive with those of specialized algorithms: a 92-colouring for a random graph (p = 0.5), hidden k-colourings in equipartite graphs (p = 0.5) for k ≤ 60 and improved results for geometric graphs. An interesting aspect is that most of our results were obtained using the precise opposite of the well-known first-fail principle.

The splitting off operation for graphs is defined in the following way: Let G be a graph. Given incident edges x = vv1 and y = vv2 in G, we can construct a new graph Gxy by adding the edge v1v2 and deleting the edges x and y. If v1 = v2, then the resulting loop is deleted. The transition from G to Gxy is called the splitting off operation. The splitting off operation has important applications in graph theory (for example, see Frank A., Augmenting graphs to meet edge-connectivity requirements, SIAM J. of Discrete Mathematics 5 No.1. (1992), 22-53; Jordan T., Edge-Splitting Problems With Demands, Springer LINK: Lecture Notes in Computer Science 1610, (1999); and Lovasz L., Combinatorial Problems and Exercises, North Holland, Amsterdam (1979)). We characterize the circuits of the graph Gxy in terms of the circuits of G.

We define the clique-width of a countable graph. We prove that a countable graph has finite clique-width iff its finite induced subgraphs have bounded clique-width. We obtain an application to a conjecture concerning the structure of sets of countable graphs having a decidable monadic second-order satisfiability problem.

The degree set D(G) of a graph G is the set of degrees of G. Given a finite, nonempty set S of positive integers, it is shown that there exists a bipartite graph G such that D ( G ) = S . In addition, the minimum order of such a graph is determined when it is either unicyclic or connected. Furthermore, for any two sets S and T of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y) such that D ( X ) = S , D ( Y ) = T . Moreover, the minimum of order of such a connected bipartite graph is obtained.