Graph Transformations preserving the stability number
Graph Chatbot
Chat with Graph Search
Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...
Clustering on graphs has been studied extensively for years due to its numerous applications. However, in contrast to the classic problems, clustering in mobile and online social networks brings new challenges. In these scenarios, it is common that observa ...
We present a new approach to matching graphs embedded in R2 or R3. Unlike earlier methods, our approach does not rely on the similarity of local appearance features, does not require an initial alignment, can handle partial matches, and can cope with non-l ...
This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously publish ...
The obstacle number of a graph G is the smallest number of polygonal obstacles in the plane with the property that the vertices of G can be represented by distinct points such that two of them see each other if and only if the corresponding vertices are jo ...
The obstacle number of a graph G is the smallest number of polygonal obstacles in the plane with the property that the vertices of G can be represented by distinct points such that two of them see each other if and only if the corresponding vertices are jo ...
Two subsets of vertices in a graph are called homometric if the multisets of distances determined by them are the same. Let h(n) denote the largest number h such that any connected graph of n vertices contains two disjoint homometric subsets of size h. It ...
We define the crossing number for an embedding of a graph G into R^3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the space crossing numbers of pseudo-random graphs. ...
Artificial neural networks, electronic circuits, and gene networks are some examples of systems that can be modeled as networks, that is, as collections of interconnected nodes. In this paper we introduce the concept of terminal graph (t-graph for short), w ...
Various practical applications of the average (A) and difference (D) of Friedel opposites are described. Techniques based on the resonant-scattering contribution to Friedel differences are applied to see whether a crystal is centrosymmetric or not, and to ...
