Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...
Steinhaus graphs on n vertices are certain simple graphs in bijective correspondence with binary {0,1}-sequences of length n-1. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic ...
We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite graph. We define a notion of scaling using the graph analogue of the Fourier domain, namely the space of eigenfunctions forming the sp ...
It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...
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 ...
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general NP-complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we presen ...
We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work ...
We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [xi,xj], c(xi)=c(xj) and for every arc (xp,xq), $c(x_{p})
We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non ...
We present a general framework for studying global complete synchronization in networks of dynamical systems with asymmetrical connections. We extend the connection graph stability method, originally developed for symmetrically coupled networks, to the gen ...
