Concept

Théorème des quatre couleurs

Publications associées (32)

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

Minimal graphs for 2-factor extension

Dominique de Werra

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

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Form finding in elastic gridshells

Pedro Miguel Nunes Pereira de Almeida Reis, Changyeob Baek

Elastic gridshells comprise an initially planar network of elastic rods that are actuated into a shell-like structure by loading their extremities. The resulting actuated form derives from the elastic buckling of the rods subjected to inextensibility. We s ...

2018

Unsplittable coverings in the plane

János Pach

A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...

Academic Press Inc Elsevier Science2016

Unsplittable Coverings in the Plane

János Pach

Springer-Verlag Berlin2016

Well-Posedness, Regularity, and Convergence Analysis of the Finite Element Approximation of a Generalized Robin Boundary Value Problem

Alfio Quarteroni, Luca Dede', Claudia Maria Colciago

In this paper, we propose the mathematical and finite element analysis of a second-order partial differential equation endowed with a generalized Robin boundary condition which involves the Laplace--Beltrami operator by introducing a function space $H^1(\O ...

Society for Industrial and Applied Mathematics2015

Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors

Bartosz Maria Walczak

Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number Θ(log log n). ...

2013

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Bartosz Maria Walczak, Michal Lason

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...

Springer US2013

On the Performance of Percolation Graph Matching

Matthias Grossglauser, Lyudmila Yartseva

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...

ACM2013

Graph Chatbot

Chattez avec Graph Search

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.

Connectez-vous pour utiliser Chat avec Graph Search