m
• E

F Nous contacter

0

Documents  05C15 | enregistrements trouvés : 53

O

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Coloring graphs on surfaces Esperet, Louis | CIRM H

Post-edited

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Colouring graphs with no odd holes, and other stories Seymour, Paul D. | CIRM

Post-edited

The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:

For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.

Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:

For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.

Both results have quite pretty proofs, which will more-or-less be given in full.
The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Le problème Graph Motif - Partie 1 Fertin, Guillaume | CIRM H

Post-edited

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Combinatorics and graphs.Selected papers based on the presentations at the twentieth anniversary conference of IPM on combinatoricsTehran # may 15-21, 2009 Brualdi, Richard A. ; Hedayat, Samad ; Kharaghani, Hadi ; Khosrovshahi, Gholamreza B. ; Shahriari, Shahriar | American Mathematical Society 2010

Congrès

- ix; 264 p.
ISBN 978-0-8218-4865-4

Contemporary mathematics , 0531

Localisation : Collection 1er étage

analyse combinatoire # théorie des graphes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Graph colouring and applications :workshop on ... held at the Centre de Recherche Mathématiques (CRM)#May 5-9 Hansen, Pierre ; Marcotte, Odile | American Mathematical Society 1999

Congrès

- 148 p.
ISBN 978-0-8218-1955-5

CRM proceedings & lecture notes , 0023

Localisation : Collection 1er étage

application # coloration par liste # coloration totale # coloriage de graphe # combinatoire # emboîtage de graphe # fréquence d"assignement # polynôme caractéristique # polynôme chromatique # théorie des graphes # énumération

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Graph theory and algorithms :proceedings of the 17th symposium of research institute of eletrical communica tion#Oct. 24-25 Nishizeki, T. ; Saito , N. | Springer-Verlag 1981

Congrès

- 216 p.
ISBN 978-3-540-10704-0

Lecture notes in computer science , 0108

Localisation : Collection 1er étage

algorithme # graphe # théorie des graphes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Graphs, morphisms and statistical physics :DIMACS workshop on ... held at Rutgers University#March 19-21 Nesetril, Jaroslav ; Winkler, P. | American Mathematical Society 2004

Congrès

- 193 p.
ISBN 978-0-8218-3551-7

DIMACS series in discrete mathematics and theorerical computer science , 0063

Localisation : Collection 1er étage

théorie graphe # morphisme # physique statistique # percolation # graphe aléatoire # modèle à forte contrainte # phase de transition # combinatoire # homomorphisme

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Hypergraph seminarproceedings of the first working seminar on hypergraphsheld at the Ohio State UniversityAug. 16 - Sept. 6 Berge, Claude ; Ray-Chaudhuri, Dijen | Springer-Verlag 1974

Congrès

ISBN 978-3-540-06846-4

Lecture notes in mathematics , 0411

Localisation : Collection 1er étage

application forte élémentaire # chromial # clique d'hypergraphes q- parti h-complets # complémentaire d'hypergraphe fortement isomorphe à hypergrap # conjecture de V. Chvátal # cycle de longueur # facettes de polyèdres 1- assortis # famille d'intersections de bords # graphe # graphe orienté # graphe représentatif d'hypergraphe h-parti complet # géométrie transversale # hypergraphe bichromatique # hypergraphe général # hypermatroïde # matroïde # nombre chromatique # nombre de coloration # partition de triples en systèmes de triples de Steiner # plan # problème extrémal # produit direct d'hypergraphes # propriété héréditaire # reconstruction d'hypergraphe # semi- noyau # théorème de Berge et Fournier # théorème du minimax application forte élémentaire # chromial # clique d'hypergraphes q- parti h-complets # complémentaire d'hypergraphe fortement isomorphe à hypergrap # conjecture de V. Chvátal # cycle de longueur # facettes de polyèdres 1- assortis # famille d'intersections de bords # graphe # graphe orienté # graphe représentatif d'hypergraphe h-parti complet # géométrie transversale # hypergraphe bichromatique # hypergraphe général # hypermatroïde # matroïde # ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Séminaire Bourbaki. Vol. 1977/78exposés 507-524, avec table par noms d'auteurs de 1967/68 à 1977/78 | Springer-Verlag 1978

Congrès

ISBN 978-3-540-09243-8

Lecture notes in mathematics , 0710

Localisation : Collection 1er étage

categories # coloriages des cartes # combinatoire # cribles # demonstration de furstenberg # equation differentielle algebrique # espace de concordances # faisceaux # fibres # groupe semi simple # logique # quatre couleurs # sphere # systeme differentiel # systeme micro differentiel # theoreme d'incompletude # varietes kahleriennes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Surveys in combinatorics, 1997 :proceedings of the British combinatorial conference#July Bailey, R. A. | Cambridge University Press 1997

Congrès

- 338 p.
ISBN 978-0-521-59840-8

London mathematical society lecture note series , 0241

Localisation : Collection 1er étage

combinatoire # conception de bloc # courbe algébrique # graphe d'interval # géométrie finie et combinatoire # mesure de connectivité # méthode de calcul # ordre d'intervale # théorie chromatique des graphes # théorie combinatoire # théorie des graphes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Coloring graphs with forbidden induced paths Chudnovsky, Maria | CIRM H

Multi angle

Combinatorics

The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2) For which graphs $H$ are there finitely many 4-critical $H$-free graphs? This talk will survey recent progress on these questions, and in particular give a complete answer to the second one. The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Induced cycles and coloring Chudnovsky, Maria | CIRM

Multi angle

A hole in a graph is an induced cycle of length at least four, and an odd hole is a hole of odd length. A famous conjecture of A. Gyárfás [1] from 1985 asserts:
Conjecture 1: For all integers $k,l$ there exists $n(k,l)$ such that every graph $G$ with no clique of carnality more than $k$ and no odd hole of length more than $l$ has chromatic number at most $n(k,l)$.

In other words, the conjecture states that the family of graphs with no long odd holes is $\chi$-bounded. Little progress was made on this problem until recently Scott and Seymour proved that Conjecture 1 is true for all pairs $(k,l)$ when $l=3$ (thus excluding all odd holes guarantees $\chi$-boundedness) [3].
No other cases have been settled, and here we focus on the case $k=2$. We resolve the first open case, when $k=2$ and $l=5$, proving that
Theorem 1. Every graph with no triangle and no odd hole of length $>5$ is $82200$-colorable.

Conjecture 1 has a number of other interesting special cases that still remain open; for instance
* Conjecture: For all $l$ every triangle-free graph $G$ with sufficiently large chromatic number has an odd hole of length more than $l$;
* Conjecture: For all $k,l$ every graph with no clique of size more than $k$ and sufficiently large chromatic number has a hole of length more than $l$.

We prove both these statements with the additional assumption that $G$ contains no $5$-hole. (The latter one was proved, but not published, by Scott earlier, improving on [2]). All the proofs follows a similar outline. We start with a leveling of a graph with high chromatic number, that is a classification of the vertices by their distance from a fixed root. Then the graph undergoes several rounds of "trimming" that allows us to focus on a subgraph $M$ with high chromatic number that is, in some sense, minimal. We also ensure that certain pairs of vertices with a neighbor in $M$ can be joined by a path whose interior is anticomplete to $M$. It is now enough to find two long paths between some such pair of vertices, both with interior in $M$ and of lengths of different parity, to obtain a long odd hole.
A hole in a graph is an induced cycle of length at least four, and an odd hole is a hole of odd length. A famous conjecture of A. Gyárfás [1] from 1985 asserts:
Conjecture 1: For all integers $k,l$ there exists $n(k,l)$ such that every graph $G$ with no clique of carnality more than $k$ and no odd hole of length more than $l$ has chromatic number at most $n(k,l)$.

In other words, the conjecture states that the family of graphs with no long odd ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Le problème Graph Motif - Partie 2 Fertin, Guillaume | CIRM H

Multi angle

Combinatorics;Computer Science;Mathematics in Science and Technology

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Restricted types of matchings Rautenbach, Dieter | CIRM H

Multi angle

Combinatorics;Computer Science

We present new results concerning restricted types of matchings such as uniquely restricted matchings and acyclic matchings, and we also consider the corresponding edge coloring notions. Our focus lies on bounds, exact and approximative algorithms. Furthermore, we discuss some matching removal problems. The talk is based on joined work with J. Baste, C. Lima, L. Penso, I. Sau, U. Souza, and J. Szwarcfiter.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

A course in topological combinatorics de Longueville, Mark | Springer 2013

Ouvrage

- xii; 238 p.
ISBN 978-1-4419-7909-4

Universitext

Localisation : Ouvrage RdC (DELO)

topologie # topologie combinatoire # théorie des graphes #topologie algébrique # théorie de Smith # conjecture de Kneser # théorème de Borsuk et Ulam # théorème du point fixe de Brouwer # lemme de Spencer # lemme de Tucker # complexe de Lovasz # théorème de Kuratowski # nombre chromatique

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

A Sharp threshold for random graphs with a monochromatic triangle in every Edge coloring Friedgut, Ehud ; Rödl, Vojtech ; Rucinski, Andrzej ; Tetali, Prasad | American Mathematical Society 2006

Ouvrage

- 66 p.
ISBN 978-0-8218-3825-9

Memoirs of the american mathematical society , 0845

Localisation : Collection 1er étage

coloriage de graphe # théorie de Ramsey # graphe aléatoire # phénomène de seuil # lemme de régularité de Szemoridi

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Algebraic combinatorics Godsil, C. D. | Chapman & Hall 1993

Ouvrage

- xv; 362 p.
ISBN 978-0-412-04131-0

Localisation : Ouvrage RdC (GODS)

analyse combinatoire # polynôme orthogonal

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Algorithmes de graphes avec programmes en Pascal Prins, Christian | Eyrolles 1994

Ouvrage

ISBN 978-2-212-09020-8

Les éditions Eyrolles

Localisation : Disparu

algorithme et graphe # arbre et arborescence # boîte à outils de graphes # chemin optimal # coloration # complexité d'algorithme # composante fortement connexe # construction de liste de prédécesseurs # décomposition de graphe en niveaux # exploration de graphe # flot et couplage # graphe orienté # parcours et connexité # parcours eulérien et hamiltonien # programme en Pascal # résolution de problème difficile

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

An atlas of graphs Read, Ronald c. ; Wilson , Robin J. | Clarendon Press 1998

Ouvrage

- 454 p.
ISBN 978-0-19-853289-7

atlas # graphe # théorie des graphes

05C15

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Axiom of choice Herrlich, Horst | Springer 2006

Ouvrage

- 194 p.
ISBN 978-3-540-30989-5

Lecture notes in mathematics , 1876

Localisation : Collection 1er étage

axiome du choix

Filtrer

Langue

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z