Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

Group : Graphs, ALgorithms and Combinatorics

Graphs and Colors: Edge-colored graphs, edge-colorings and proper connections.

Starts on 01/12/2009
Advisor : MANOUSSAKIS, Yannis

Funding : contrat doctoral UPS
Affiliation : Université Paris-Sud
Laboratory : LRI

Defended on 13/12/2012, committee :
Rapporteurs :
Professeur Michel Habib - Université Paris Diderot.
Professeur Mickael Montassier - Université Montpellier 2.
Examinateurs :
Professeur Dominique Barth - Université de Versailles.
Professeur Alain Denise - Université Paris-Sud 11.
Professeur Marina Groshaus - Universidad de Buenos Aires.
Directeur :
Professeur Yannis Manoussakis - Université Paris-Sud 11.

Research activities :

Abstract :
In this thesis, we study different problems in edge-colored graphs and edge-colored multigraphs, such as proper connection, strong edge colorings, and proper hamiltonian paths and cycles. Finally, we improve the known $O(n^4)$ algorithm to decide the behavior of a graph under the biclique operator, by studying bicliques in graphs without false-twin vertices. In particular,
- We first study the $k$-proper-connection number of graphs, this is, the minimum number of colors needed to color the edges of a graph such that between any pair of vertices there exist $k$ internally vertex-disjoint paths. We denote this number $pc_k(G)$. We prove several upper bounds for $pc_k(G)$. We state some conjectures for general and bipartite graphs, and we prove all of them for the case $k=1$.
- Then, we study the existence of proper hamiltonian paths and proper hamiltonian cycles in edge-colored multigraphs. We establish sufficient conditions, depending on several parameters such as the number of edges, the rainbow degree, the connectivity, etc.
- Later, we show that the strong chromatic index is linear in the maximum degree for any $k$-degenerate graph where $k$ is fixed. As a corollary, our result leads to considerable improvement of the constants and also gives an easier and more efficient algorithm for this familly of graphs. Next, we consider outerplanar graphs. We give a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improve the upper bound for general outerplanar graphs from the $3Delta-3$ bound.
- Finally, we study bicliques in graphs without false-twin vertices and then we present an $O(n+m)$ algorithm to recognize convergent and divergent graphs improving the $O(n^4)$ known algorithm.

More information:\_MONTERO\_LEANDRO\_13122012.pdf
Ph.D. dissertations & Faculty habilitations
The original manuscript conceptualizes the recent rise of digital platforms along three main dimensions: their nature of coordination devices fueled by data, the ensuing transformations of labor, and the accompanying promises of societal innovation. The overall ambition is to unpack the coordination role of the platform and where it stands in the horizon of the classical firm – market duality. It is also to precisely understand how it uses data to do so, where it drives labor, and how it accommodates socially innovative projects. I extend this analysis to show continuity between today’s society dominated by platforms and the “organizational society”, claiming that platforms are organized structures that distribute resources, produce asymmetries of wealth and power, and push social innovation to the periphery of the system. I discuss the policy implications of these tendencies and propose avenues for follow-up research.