Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...

Elsevier2008

Graph coloring with cardinality constraints on the neighborhoods

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...

2009

On the inapproximability of independent domination in 2P3-free perfect graphs

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...

2009

Bicolored matchings in some classes of graphs

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Minimal graphs for 2-factor extension

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Minimum d-blockers and d-transversals in graphs

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

A note on chromatic properties of threshold graphs

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...

Elsevier2012

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...

2012

Graph Transformations preserving the stability number

We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...

Elsevier Science Bv2012

Graph transformations preserving the stability number

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...

2009

Blockers and transversals

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

Elsevier2009

Recoloring subgraphs of K-2n for sports scheduling

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. Thi ...

ELSEVIER2021

Partitioning cographs into cliques and stable sets

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005

Optimal pathway reconstruction on 3D NMR maps

A three-dimensional Nuclear Magnetic Resonance (NMR) map displays the results of NMR experiments, that allow to determine the shape of a biological molecule. Shape calculation starts from a reconstruction of a sequence of NMR signals, which is equivalent t ...

Elsevier Science Bv2015

On two coloring problems in mixed graphs

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 str ...

2008

Polarity of chordal graphs

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...

2008

On some coloring problems in grids

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...

2013

A tutorial on the use of graph coloring for some problems in robotics

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...

2009

A Magnetic Procedure for the Stability Number