Refine my results

• Articles

• Fribourg

Domain

• Medicine, Technology, Engineering

On Split B1-EPG Graphs

In: Lecture Notes in Computer Science, 2018, vol. 10807, p. 361-375

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are...

Public access from Dec 18, 2019

Characterising Chordal Contact : Bo-VPG Graphs

In: Lecture Notes in Computer Science, 2018, vol. 10856, p. 89-100

A graph G is a Bo- VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact Bo- VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph...

On two coloring problems in mixed graphs

In: European Journal of Combinatorics, 2008, vol. 29, p. 712-125

We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one, we want adjacent vertices to have different colors and the tail of an arc to get a color strictly less than a color of the head of this arc; in the second problem, we also allow vertices linked by an arc to have the same color....

Blockers and transversals

In: Discrete Mathematics, 2009, vol. 309, p. 4306-4314

Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular...

Graph coloring with cardinality constraints on the neighborhoods

In: discrete Optimization, 2009, vol. 6, no. 4, p. 362-369

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph a k-coloring, i.e., a partition (V_1,\cdots,V_k) of the vertex set of G such that, for some specified neighborhood \tilde|{N}(v) of each vertex v, the number of vertices in \tilde|{N}(v)\cap V_i is (at most) a given integer h_i^v. The complexity of some...

Mixed graph edge coloring

In: Discrete Mathematics, 2009, vol. 309, no. 12, p. 4027-4036

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NP-completeness results for the case of outerplanar...

Public access from Mar 5, 2020

Graphs vertex-partitionable into strong cliques

In: Discrete Mathematics, 2018, vol. 341, p. 1392-1405

A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by Yamashita and Kameda in 1999 and form a rich class of well- covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several...

A Boundary Property for Upper Domination

In: Lecture Notes in Computer Science, 2016, vol. 9843, p. 229-240

An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating...

Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

In: Lecture Notes in Computer Science, 2016, vol. 9849, p. 38-49

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are...

Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions

In: Lecture Notes in Computer Science, 2017, vol. 10185, p. 470-483

Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these...