Search

The first combinatorial algorithm for the minimum weighted clique cover (MWCC) in a claw‐free perfect graph G due to Hsu and Nemhauser dates back to 1984. It is essentially a "dual" algorithm as it relies on any algorithm for the maximum weighted stable set (MWSS) problem in claw‐free graphs and, taking into account the best‐known complexity for the latter problem, its complexity is O(∣V(G)∣5). More recently, Chudnovsky and Seymour introduced a composition operation, strip composition, to define their structural results for claw‐free graphs; however, this composition operation is general and applies to nonclaw‐free graphs as well. In this paper, we show that an MWCC of a perfect strip‐composed graph, with the basic graphs belonging to a class G, can be found in polynomial time, provided that the MWCC problem can be solved on G in polynomial time. For the case of claw‐free perfect strip‐composed graphs, the algorithm can be tailored so that it never requires the computation of an MWSS on the strips and can be implemented as to run in O(∣V(G)∣3) time. Finally, building upon several results from the literature, we show how to deal with nonstrip‐composed claw‐free perfect graphs, and therefore compute an MWCC in a general claw‐free perfect graph in O(∣V(G)∣3) time. [ABSTRACT FROM AUTHOR]

Graphs with bounded thinness were defined in 2007 as a generalization of interval graphs. In this paper we introduce the concept of proper thinness, such that graphs with bounded proper thinness generalize proper interval graphs. We study the complexity of problems related to the computation of these parameters, describe the behavior of the thinness and proper thinness under three graph operations, and relate thinness and proper thinness to other graph invariants in the literature. Finally, we describe a wide family of problems that can be solved in polynomial time for graphs with bounded thinness, generalizing for example list matrix partition problems with bounded size matrix, and enlarge this family of problems for graphs with bounded proper thinness, including domination problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2 -domination number, γ w 2 ( G ) , the 2 -domination number, γ 2 ( G ) , the { 2 } -domination number, γ { 2 } ( G ) , the double domination number, γ × 2 ( G ) , the total { 2 } -domination number, γ t { 2 } ( G ) , and the total double domination number, γ t × 2 ( G ) , where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γ R ( G ) , and two classical parameters, the domination number, γ ( G ) , and the total domination number, γ t ( G ) , we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. [ABSTRACT FROM AUTHOR]

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called $$B_0$$ -VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal $$B_0$$ -VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of $$B_0$$ -VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for $$B_0$$ -VPG graphs in the class of block graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2 -clique colorable. In this paper we prove that B 1 -EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4 -clique colorable. Moreover, given a B 1 -EPG representation of a graph, we provide a linear time algorithm that constructs a 4 -clique coloring of it. [ABSTRACT FROM AUTHOR]

We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the k th powers of the graphs are of clique-width at most ℓ . We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k , there exists a graph class such that the k th powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. [ABSTRACT FROM AUTHOR]

We consider the following vertex-partition problem on graphs, known as the CLUSTER DELETION (CD) problem: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case, cliques) to minimize the total weight of edges outside the clusters. The decision version of this optimization problem is known to be NP-complete even for unweighted graphs and has been studied extensively. We investigate the complexity of the decision CD problem for the family of chordal graphs, showing that it is NP-complete for weighted split graphs, weighted interval graphs and unweighted chordal graphs. We also prove that the problem is NP-complete for weighted cographs. Some polynomial-time solvable cases of the optimization problem are also identified, in particular CD for unweighted split graphs, unweighted proper interval graphs and weighted block graphs. [ABSTRACT FROM AUTHOR]

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph $$G$$ , denoted by $$\chi _b(G)$$ , is the maximum number $$t$$ such that $$G$$ admits a b-coloring with $$t$$ colors. A graph $$G$$ is called b-continuous if it admits a b-coloring with $$t$$ colors, for every $$t = \chi (G),\ldots ,\chi _b(G)$$ , and b-monotonic if $$\chi _b(H_1) \ge \chi _b(H_2)$$ for every induced subgraph $$H_1$$ of $$G$$ , and every induced subgraph $$H_2$$ of $$H_1$$ . We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: (1) We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. (2) We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at least a given threshold. (3) We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. (4) Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic. [ABSTRACT FROM AUTHOR]

A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an O ( n 2 ) -time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class 2 with respect to edge-coloring. [ABSTRACT FROM AUTHOR]

A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs. [ABSTRACT FROM AUTHOR]

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness ofP4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for anyP4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced. [ABSTRACT FROM PUBLISHER]

Abstract: Given integers , the weighted clique graph of is the clique graph , in which there is a weight assigned to each complete set of size of , for each . This weight equals the cardinality of the intersection of the cliques of corresponding to . We characterize weighted clique graphs in similar terms as Roberts and Spencer’s characterization of clique graphs. Further we characterize several classical graph classes in terms of their weighted clique graphs, providing a common framework for describing some different well-known classes of graphs, as hereditary clique-Helly graphs, split graphs, chordal graphs, interval graphs, proper interval graphs, line graphs, among others. [Copyright &y& Elsevier]

In this paper, we study the minimum sum coloring (MSC) problem on P-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P-sparse graphs. [ABSTRACT FROM AUTHOR]

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. [ABSTRACT FROM AUTHOR]

Abstract: A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. [Copyright &y& Elsevier]

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe 풢) graphs with disconnected complement for every graph class 풢 with a companion. [ABSTRACT FROM AUTHOR]

Abstract: The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer , the maximum edge subgraph problem consists of finding a -vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work. [Copyright &y& Elsevier]

Abstract: We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the -coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the -coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique-trees of different heights, providing polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain -coloring, -coloring, -coloring, and list-coloring. Second, clique-trees of height 2 are the first known example of a class of graphs where -coloring is polynomial-time solvable and precoloring extension is NP-complete, thus being at the same time the first example where -coloring is polynomially solvable and -coloring is NP-complete. Last, we show that the-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Bonomo et al. [F. Bonomo, G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3–16]. [Copyright &y& Elsevier]

Abstract: The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into stacks of size that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem. In the paper, we show that the PDTC problem can be solved in polynomial time when the number of stacks is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, is the number of colors and is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when is a fixed constant, but is unbounded. [Copyright &y& Elsevier]

Abstract: A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, -tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property. [Copyright &y& Elsevier]

Abstract: In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of positive integers to each vertex of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees. [ABSTRACT FROM AUTHOR]

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k. In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3. [ABSTRACT FROM AUTHOR]

Abstract: A -coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The -chromatic number of a graph , denoted by , is the maximum number such that admits a -coloring with colors. A graph is -continuous if it admits a -coloring with colors, for every , and it is -monotonic if for every induced subgraph of , and every induced subgraph of . In this work, we prove that -tidy graphs (a generalization of many classes of graphs with few induced s) are -continuous and -monotonic. Furthermore, we describe a polynomial time algorithm to compute the-chromatic number for this class of graphs. [Copyright &y& Elsevier]

Abstract: Bilateral investment treaties (BITs) are agreements between two countries for the reciprocal encouragement, promotion and protection of investments in each other’s territories by companies based in either country. Germany and Pakistan signed the first BIT in 1959 and since then, BITs are one of the most popular and widespread form of international agreement. In this work we study the proliferation of BITs using a social networks approach. We propose a network growth model that dynamically replicates the empirical topological characteristics of the BIT network. [Copyright &y& Elsevier]

Abstract: A graph is clique-perfect if the cardinality of a maximum clique-independent set of equals the cardinality of a minimum clique-transversal of , for every induced subgraph of . A graph is coordinated if the minimum number of colors that can be assigned to the cliques of in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of with a common vertex, for every induced subgraph of . Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, , bull}-free, both superclasses of triangle-free graphs. [Copyright &y& Elsevier]

Abstract: A clique-transversal of a graph is a subset of vertices that meets all the cliques of . A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of . The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs. [Copyright &y& Elsevier]

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ b( G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every $$t = \chi(G), \ldots, \chi_b(G)$$ . We define a graph G to be b-monotonic if χ b( H1) ≥ χ b( H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. In this work, we prove that P4-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. [ABSTRACT FROM AUTHOR]

Abstract: A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. [Copyright &y& Elsevier]

Abstract: The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different areas, and many polynomial-time algorithms and NP-completeness proofs for this kind of problems are known. In this work we prove new NP-completeness results for these problems in some graph classes, such as interval, circular-arc, permutation, circle, bridged, weakly chordal and clique-Helly graphs. [Copyright &y& Elsevier]

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. [ABSTRACT FROM AUTHOR]

Abstract: A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs. [Copyright &y& Elsevier]