Search

A large number of NP-hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider mim-width, a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is "quickly computable" for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph H, the class of H-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for (H₁,H₂)-free graphs. We identify several general classes of (H₁,H₂)-free graphs having unbounded clique-width, but bounded mim-width, illustrating the power of mim-width. Moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time, for these classes. Hence, as mentioned, these results have algorithmic implications: when the input is restricted to such a class of (H₁,H₂)-free graphs, many problems become polynomial-time solvable, including classical problems such as k-Colouring and Independent Set, domination-type problems known as LC-VSVP problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain H₁ and H₂, the class of (H₁,H₂)-free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results, which give both new bounded and unbounded cases for mim-width, with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for (H₁,H₂)-free graphs. In particular, we classify the mim-width of (H₁,H₂)-free graphs for all pairs (H₁,H₂) with |V(H₁)| + |V(H₂)| ≤ 8. When H₁ and H₂ are connected graphs, we classify all pairs (H₁,H₂) except for one remaining infinite family and a few isolated cases., LIPIcs, Vol. 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), pages 6:1-6:18

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight., Comment: 22 pages, 1 figure

The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes., 10 pages. Accepted for J. Graph Theory

We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets I and J of a graph G, both of size at least k, is it possible to transform I into J by adding and removing vertices one-by-one, while maintaining an independent set of size at least k throughout? This problem is known to be PSPACE-hard in general. For the case that G is a cograph on n vertices, we show that it can be solved in time O(n2), and that the length of a shortest reconfiguration sequence from I to J is bounded by 4n−2k (if it exists). More generally, we show that if G is a graph class for which (i) TAR-Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in G using disjoint union and complete join operations. Chordal graphs and claw-free graphs are given as examples of such a class G.

In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example-in a certain sense, every graph with large treewidth "contains" LKn. However, the treewidth of LKn was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.

A graph G is called H-saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph G+e contains some H. The minimum size of an n-vertex H-saturated graph is denoted by sat(n,H). We prove sat(n,Ck)=n+n/k+O((n/k2)+k2) holds for all n≥k≥3, where Ck is a cycle with length k. A graph G is H-semisaturated if G+e contains more copies of H than G does for ∀e∈E(G¯). Let ssat (n,H) be the minimum size of an n-vertex H-semisaturated graph. We have ssat(n,Ck)=n+n/(2k)+O((n/k2)+k). We conjecture that our constructions are optimal for n>n0(k). © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013

The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if G is a bipartite (2k + 1)-regular graph that is Hamilton decomposable, then the line graph, L(G), of G is also Hamilton decomposable. A similar result is obtained for 5-regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley & Sons, Inc.

The k-biclosure of a balanced bipartite graph wiht color classes A and B is the graph obtained from G by recursively joining pairs of nonadjacent vertices respectively taken in A and B whose degree sum is at least k, until no such pair remains. A property P defined on all the balanced bipartite graphs of order 2n is k-bistable if whenever G + ab has property P and dG(b) ≧ k then G itself has property P. We present a synthesis of results involving, for some properties, P, the bistability of P, the k-biclosure of G, the number of edges and the minimum degree. © 1995 John Wiley & Sons, Inc.

The analysis and synthesis of reliable large-scale networks typically involve a graph theoretic model. We give a survey of the graph theoretic notions which are relevant to the synthesis problem. It is shown how a number of unsolved graph extremal problems relate to the synthesis question.

The biparticity β(G) of a graph G is the minimum number of bipartite graphs required to cover G. It is proved that for any graph G, β(G) = {log2χ(G)}. In view of the recent announcement of the Four Color Theorem, it follows that the biparticity of every planar graph is 2.