Graph-Theoretic Concepts in Computer Science

Due to its ease of use, as well as its enormous flexibility in its degree structure, the configuration model has become the network model of choice in many disciplines. It has the wonderful property, that, conditioned on being simple, it is a uniform random graph with the prescribed degrees. This is a beautiful example of a general technique called the probabilistic method that was pioneered by Erdős. It allows us to count rather precisely how many graphs there are with various degree structures. As a result, the configuration model is often used as a null model in network theory, so as to compare real-world network data to. When the degrees are sufficiently light-tailed, the asymptotic probability of simplicity for the configuration model can be explicitly computed. Unfortunately, when the degrees vary rather extensively and vertices with very high degrees are present, this method fails. Since such degree sequences are frequently reported in empirical work, this is a major caveat in network theory.In this survey, we discuss recent results for the configuration model, including asymptotic results for typical distances in the graph, asymptotics for the number of self-loops and multiple edges in the finite-variance case. We also discuss a possible fix to the problem of non-simplicity, and what the effect of this fix is on several graph statistics. Further, we discuss a generalization of the configuration model that allows for the inclusion of community structures. This model removes the flaw of the locally tree-like nature of the configuration model, and gives a much improved fit to real-world networks.

Bubbles are pairs of internally vertex-disjoint (s, t)-paths with applications in the processing of DNA and RNA data. For example, enumerating alternative splicing events in a reference-free context can be done by enumerating all bubbles in a de Bruijn graph built from RNA-seq reads [16]. However, listing and analysing all bubbles in a given graph is usually unfeasible in practice, due to the exponential number of bubbles present in real data graphs. In this paper, we propose a notion of a bubble generator set, i.e. a polynomial-sized subset of bubbles from which all the others can be obtained through the application of a specific symmetric difference operator. This set provides a compact representation of the bubble space of a graph, which can be useful in practice since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. Furthermore, we provide a polynomial-time algorithm to decompose any bubble of a graph into the bubbles of such a generator in a tree-like fashion.

In the Critical Node Cut problem, given an undirected graph G and two non-negative integers k and $$\mu $$μ, the goal is to find a set S of exactly k vertices such that after deleting S we are left with at most $$\mu $$μ connected pairs of vertices. Back in 2015, Hermelin et al. studied the aforementioned problem under the framework of parameterized complexity. They considered various natural parameters, namely, the size k of the desired solution, the upper bound $$\mu $$μ on the number of remaining connected pairs, the lower bound b on the number of connected pairs to be removed, and the treewidth $$\mathsf {tw}(G)$$tw(G) of the input graph G. For all but one combinations of the above parameters, they determined whether Critical Node Cut is fixed-parameter tractable and whether it admits a polynomial kernel. The only question they left open is whether the problem remains fixed-parameter tractable when parameterized by $$k + \mathsf {tw}(G)$$k+tw(G). We answer this question in the negative via a new problem of independent interest, which we call SumCSP. We believe that SumCSP can be a useful starting point for showing hardness results of the same nature, i.e. when the treewidth of the graph is part of the parameter.

In this paper we consider graphs whose edges are associated with a degree of importance, which may depend on the type of connections they represent or on how recently they appeared in the scene, in a streaming setting. The goal is to construct layouts in which the readability of an edge is proportional to its importance, that is, more important edges have fewer crossings. We formalize this problem and study the case in which there exist three different degrees of importance. We give a polynomial-time testing algorithm when the graph induced by the two most important sets of edges is biconnected. We also discuss interesting relationships with other constrained-planarity problems.

A graph is k-planar $$(k \ge 1)$$(k≥1) if it can be drawn in the plane such that no edge is crossed $$k+1$$k+1 times or more. A graph is k-quasi-planar $$(k \ge 2)$$(k≥2) if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for $$k \ge 3$$k≥3, every k-planar graph is $$(k+1)$$(k+1)-quasi-planar.

The extension complexity$$\mathsf {xc}(P)$$xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let $${{\mathrm{\mathsf {STAB}}}}(G)$$STAB(G) be the convex hull of the stable sets of G. It is easy to see that $$n \leqslant \mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G)) \leqslant n+m$$n⩽xc(STAB(G))⩽n+m. We improve both of these bounds. For the upper bound, we show that $$\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))$$xc(STAB(G)) is $$O(\frac{n^2}{\log n})$$O(n2logn), which is an improvement when G has quadratically many edges. For the lower bound, we prove that $$\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))$$xc(STAB(G)) is $$\varOmega (n \log n)$$Ω(nlogn) when G is the incidence graph of a finite projective plane. We also provide examples of 3-regular bipartite graphs G such that the edge vs stable set matrix of G has a fooling set of size |E(G)|.

Let $$T_{n,k}$$Tn,k be the number of labeled graphs on n vertices and treewidth at most k (equivalently, the number of labeled partial k-trees). We show that $$\left( c \frac{k\ 2^k n}{\log k} \right) ^n 2^{-\frac{k(k+3)}{2}} k^{-2k-2}\ \leqslant \ T_{n,k}\ \leqslant \ \left( k \ 2^k n\right) ^n 2^{-\frac{k(k+1)}{2}} k^{-k},$$ck2knlogkn2-k(k+3)2k-2k-2⩽Tn,k⩽k2knn2-k(k+1)2k-k,for $$k > 1$$k>1 and some explicit absolute constant $$c > 0$$c>0. Disregarding lower-order terms, the gap between the lower and upper bound is of order $$(\log k)^n$$(logk)n. The upper bound is a direct consequence of the well-known formula for the number of labeled k-trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k.

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.

In Defective Coloring we are given a graph G and two integers $$\mathrm {\chi _d},\varDelta ^*$$χd,Δ∗ and are asked if we can $$\mathrm {\chi _d}$$χd-color G so that the maximum degree induced by any color class is at most $$\varDelta ^*$$Δ∗. We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters $$\mathrm {\chi _d},\varDelta ^*$$χd,Δ∗ is set to the smallest possible fixed value that does not trivialize the problem ($$\mathrm {\chi _d}=2$$χd=2 or $$\varDelta ^*=1$$Δ∗=1). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs.We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either $$\mathrm {\chi _d}$$χd or $$\varDelta ^*$$Δ∗ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both $$\mathrm {\chi _d}$$χd and $$\varDelta ^*$$Δ∗ are unbounded.

Let I be an independent set of a graph G. Imagine that a token is located on every vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a single token move. This problem is known to be PSPACE-complete even on planar graphs.In [9], Demaine et al. asked whether the Token Sliding problem can be decided in polynomial time on interval graphs and more generally on chordal graphs. Yamada and Uehara [20] showed that a polynomial time transformation can be found in proper interval graphs.In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether an independent set I of an interval graph can be transformed into another independent set J. Moreover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this latter problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.

EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class $$B_k$$-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most k bends. Epstein et al. showed in 2013 that computing a maximum clique in $$B_1$$-EPG graphs is polynomial. As remarked in [Heldt et al. 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for $$B_2$$ and $$B_3$$-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in $$B_2$$-EPG graphs given a representation of the graph.Moreover, we show that a simple counting argument provides a $${2(k+1)}$$-approximation for the coloring problem on $$B_k$$-EPG graphs without knowing the representation of the graph. It generalizes a result of [Epstein et al. 2013] on $$B_1$$-EPG graphs (where the representation was needed).

We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that:intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class,not every intersection graph of rays is an intersection graph of downward rays, andnot every outer segment graph is an intersection graph of rays.The first result answers an open problem posed by Cabello and Jejčič. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.

Biró, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph H. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. Our paper is the first study of the recognition and dominating set problems of this large collection of intersection classes of graphs.We negatively answer the question of Biró, Hujter, and Tuza who asked whether H-graphs can be recognized in polynomial time, for a fixed graph H. Namely, we show that recognizing H-graphs is -complete if H contains the diamond graph as a minor. On the other hand, for each tree T, we give a polynomial-time algorithm for recognizing T-graphs and an $$\mathcal {O}(n^4)$$O(n4)-time algorithm for recognizing $$K_{1,d}$$K1,d-graphs. For the dominating set problem (parameterized by the size of H), we give - and -time algorithms on $$K_{1,d}$$K1,d-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides -time algorithms for the independent set and independent dominating set problems on H-graphs.

The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph G from some class $$\mathcal K$$K of “pattern graphs” can be embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter tractable if $$\mathcal K$$K is a class of graphs of bounded tree width and $$W [1]$$W[1]-complete otherwise.Towards this conjecture, we prove that the embedding problem is $$W [1]$$W[1]-complete if $$\mathcal K$$K is the class of all grids or the class of all walls.

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with $$\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} $$max5,2t-12-2 many colors. If the input graph is triangle-free, we only need $$\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} $$max4,t-12+1 many colors. The running time of our algorithm is $$O((3^{t-2}+t^2)m+n)$$O((3t-2+t2)m+n) if the input graph has n vertices and m edges.

Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network, in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk.Fleiner [13] established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting-path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the highly complex stable multicommodity flow model by Király and Pap [24]. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NP-complete to decide whether an integral solution exists.

Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether their question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs $$H_1,H_2$$H1,H2 are forbidden. We confirm it for one of the two stubborn cases, namely for the case $$(H_1,H_2)=(\text {triangle},P_2+P_4)$$(H1,H2)=(triangle,P2+P4) by proving that the class of $$(\text {triangle},P_2+P_4)$$(triangle,P2+P4)-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of $$(\text {triangle},H)$$(triangle,H)-free graphs are well-quasi-ordered.

The square of a given graph $$H=(V,E)$$H=(V,E) is obtained from H by adding an edge between every two vertices at distance two in H. Given a graph class $$\mathcal {H}$$H, the $$\mathcal {H}$$H-Square Rootproblem asks for the recognition of the squares of graphs in $$\mathcal {H}$$H. In this paper, we answer positively to an open question of [Golovach et al. IWOCA 2016] by showing that the squares of cactus-block graphs can be recognized in polynomial time. Our proof is based on new relationships between the decomposition of a graph by cut-vertices and the decomposition of its square by clique cutsets. More precisely, we prove that the closed neighbourhoods of cut-vertices in H induce maximal subgraphs of $$G = H^2$$G=H2 with no clique-cutset. Furthermore, based on this relationship, we can compute from a given graph G the block-cut tree of a desired square root (if any). Although the latter tree is not uniquely defined, we show surprisingly that it can only differ marginally between two different roots. Our approach not only gives the first polynomial-time algorithm for the $$\mathcal {H}$$H-Square Rootproblem for several graph classes $$\mathcal {H}$$H, but it also provides a unifying framework for the recognition of the squares of trees, block graphs and cactus graphs—among others.

We study the $${\mathsf {NP}}$$NP-hard Minimum Shared Edges (MSE) problem on graphs: decide whether it is possible to route p paths from a start vertex to a target vertex in a given graph while using at most k edges more than once. We show that MSE can be decided on bounded (i.e. finite) grids in linear time when both dimensions are either small or large compared to the number p of paths. On the contrary, we show that MSE remains $${\mathsf {NP}}$$NP-hard on subgraphs of bounded grids.Finally, we study MSE from a parametrised complexity point of view. It is known that MSE is fixed-parameter tractable with respect to the number p of paths. We show that, under standard complexity-theoretical assumptions, the problem parametrised by the combined parameter k, p, maximum degree, diameter, and treewidth does not admit a polynomial-size problem kernel, even when restricted to planar graphs.

Given two graphs $$H_1$$H1 and $$H_2$$H2, a graph G is $$(H_1,H_2)$$(H1,H2)-free if it contains no subgraph isomorphic to $$H_1$$H1 or $$H_2$$H2. Let $$P_t$$Pt and $$C_s$$Cs be the path on t vertices and the cycle on s vertices, respectively. In this paper we show that for any $$(P_6,C_4)$$(P6,C4)-free graph G it holds that $$\chi (G)\le \frac{3}{2}\omega (G)$$χ(G)≤32ω(G), where $$\chi (G)$$χ(G) and $$\omega (G)$$ω(G) are the chromatic number and clique number of G, respectively. Our bound is attained by $$C_5$$C5 and the Petersen graph. The new result unifies previously known results on the existence of linear $$\chi $$χ-binding functions for several graph classes. Our proof is based on a novel structure theorem on $$(P_6,C_4)$$(P6,C4)-free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time 3/2-approximation algorithm for coloring $$(P_6,C_4)$$(P6,C4)-free graphs. Our algorithm computes a coloring with $$\frac{3}{2}\omega (G)$$32ω(G) colors for any $$(P_6,C_4)$$(P6,C4)-free graph G in $$O(n^2m)$$O(n2m) time.

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding whether a given graph has a square root that belongs to a particular graph class. There are both polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of a chordal graph is at most $$1.7549^n$$1.7549n, and these can be enumerated in time $$O(1.7549^n)$$O(1.7549n). For interval graphs, we achieve the better upper bound of $$1.6957^n$$1.6957n for the number of maximal irredundant sets and we show that they can be enumerated in time $$O(1.6957^n)$$O(1.6957n). Finally, we show that forests have at most $$1.6181^n$$1.6181n maximal irredundant sets that can be enumerated in time $$O(1.6181^n)$$O(1.6181n). We complement the latter result by providing a family of forests having at least $$1.5292^n$$1.5292n maximal irredundant sets.

Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to appear) introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, referred to as the minimum distinct conflict-free row split (MDCRS) problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurović et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs.We give new formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including: (i) a strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth’s theorem, (ii) APX-hardness results for both problems, (iii) two approximation algorithms for the MCRS problem, and (iv) a 2-approximation algorithm for the MDCRS problem.

We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n / 4 straight-line segments on a polynomial grid, and with n / 2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with $$(8n\,-\,17)/3$$ segments on an $$O(n)\,\times \,O(n^2)$$ grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n / 2 edges on an $$O(n)\,\times \,O(n^2)$$ grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only $$(5n\,-\,11)/3$$ arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.

In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set $$S \subseteq V(G) \cup E(G)$$S⊆V(G)∪E(G) of cardinality at most k such that every element $$x \in (V(G) \cup E(G)) \setminus S$$x∈(V(G)∪E(G))\S is either adjacent to or incident with an element of S. We show that mds can be solved in time $${7.465^k n^{\mathcal {O}(1)}} $$7.465knO(1) on general graphs, and in time $$2^{\mathcal {O}(\sqrt{k})} n^{\mathcal {O}(1)}$$2O(k)nO(1) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time $$2^{o(k)} n^{\mathcal {O}(1)}$$2o(k)nO(1) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP$$ \subseteq \mathsf{NP / poly}$$⊆NP/poly. In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width $$\mathsf{tw}$$tw, solves mds in time $$6^{\mathsf{tw}} n^{\mathcal {O}(1)}$$6twnO(1). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time $$\mathcal {O}((2-\epsilon )^{\mathsf{tw}(G)} n^{\mathcal {O}(1)})$$O((2-ϵ)tw(G)nO(1)) for any $$\epsilon >0$$ϵ>0, where $$\mathsf{tw}(G)$$tw(G) is the tree-width of G.

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity.A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle’s serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing a fair objective function (fairMSO).We show how these fragments relate to each other in expressive power and highlight their (non)linearity. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping FPT runtime but removing linearity of either makes this impossible, and we provide an XP algorithm for the hard case. Furthemore, we show that even the combination of the two most powerful fragments is solvable in polynomial time on graphs of bounded treewidth.

A trapezoid graph is an intersection graph of trapezoids spanned between two horizontal lines. The partial representation extension problem for trapezoid graphs is a generalization of the recognition problem: given a graph G and an assignment $$\xi $$ξ of trapezoids to some vertices of G, can $$\xi $$ξ be extended to a trapezoid intersection model of the entire graph G? We show that this can be decided in polynomial time. Thus, we determine the complexity of partial representation extension for one of the two major remaining classes of geometric intersection graphs for which it has been unknown (circular-arc graphs being the other).

We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [26]. We say that a class $$\mathcal {C}$$C of graphs admits low rank-width colorings if there exist functions $$N:\mathbb {N}\rightarrow \mathbb {N}$$N:N→N and $$Q:\mathbb {N}\rightarrow \mathbb {N}$$Q:N→N such that for all $$p\in \mathbb {N}$$p∈N, every graph $$G\in \mathcal {C}$$G∈C can be vertex colored with at most N(p) colors such that the union of any $$i\le p$$i≤p color classes induces a subgraph of rank-width at most Q(i).Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class $$\mathcal {C}$$C of bounded expansion and every positive integer r, the class $$\{G^r:G\in \mathcal {C}\}$${Gr:G∈C} of rth powers of graphs from $$\mathcal {C}$$C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every graph class admitting low rank-width colorings has the Erdős-Hajnal property and is $$\chi $$χ-bounded.

A common task in phylogenetics is to find an evolutionary tree representing proximity relationships between species. This motivates the notion of leaf powers: a graph $$G = (V, E)$$G=(V,E) is a leaf power if there exist a tree T on leafset V and a threshold k such that $$uv \in E$$uv∈E if and only if the distance between u and v in T is at most k. Characterizing leaf powers is a challenging open problem, along with determining the complexity of their recognition. Leaf powers are known to be strongly chordal, but few strongly chordal graphs are known to not be leaf powers, as such graphs are difficult to construct. Recently, Nevries and Rosenke asked if leaf powers could be characterized by strong chordality and a finite set of forbidden induced subgraphs.In this paper, we provide a negative answer to this question, by exhibiting an infinite family $$\mathcal {G}$$G of (minimal) strongly chordal graphs that are not leaf powers. During the process, we establish a connection between leaf powers, alternating cycles and quartet compatibility. We also show that deciding if a chordal graph is $$\mathcal {G}$$G-free is NP-complete.

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. Only few examples of classes are available, where the problem admits polynomial-time solutions. In the present paper, we extend the short list of such classes with two new examples.

A graph $$G=(V,E)$$G=(V,E) is called equidominating if there exists a value and a weight function such that the total weight of a subset $$D\subseteq V$$D⊆V is equal to t if and only if D is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the Equidomination problem.In this paper we show that two parameterized versions of the Equidomination problem are fixed-parameter tractable: the first parameterization considers the target value t leading to the Target-tEquidomination problem. The second parameterization allows only weights up to a value k, which yields the k-Equidomination problem.In addition, we characterize the graphs whose every induced subgraph is equidominating. We give a finite forbidden induced subgraph characterization and derive a fast recognition algorithm.

We prove that every 4-connected planar triangulation admits a contact representation by homothetic triangles.There is a known proof of this result that is based on the Convex Packing Theorem by Schramm, a general result about contact representations of planar triangulations by convex shapes. But our approach makes use of the combinatorial structure of triangle contact representations in terms of Schnyder woods. We start with an arbitrary Schnyder wood and produce a sequence of Schnyder woods via face flips. We show that at some point the sequence has to reach a Schnyder wood describing a representation by homothetic triangles.