Séminaire d'Algorithmique du plateau de Saclay

Le séminaire d'algorithmique du plateau de Saclay est organisé toutes les deux semaines, le vendredi après-midi au LIX.

Séminaires récents et à venir

VERTEX DISTINGUISHING COLORINGS OF GRAPHS

-- Professor Mariusz Wozniak (Department of Discrete Mathematics, AGH University, Cracow, Poland)

Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to ...

The coloring problem in clique-hypergraphs of graphs

-- Pr. Liying Kang (Department of Mathematics, Shanghai University, China)

ABSTRACT: A maximal clique of a graph is a clique not properly contained in any other clique. A \(k\)-clique coloring of a graph is an assignment of a \(k\) colors to the vertices of \(G\) such that no maximal clique with at least two vertices is monochromatic. The clique-chromatic ...

Minimizing the number of unhappy singles

-- Chien-Chung Huang (Gothenburg)

Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties. A matching M is said to be stable if there is ...

See all

Translations: en