m
• E

F Nous contacter

0

# Documents  Seymour, Paul D. | enregistrements trouvés : 4

O

P Q

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

Combinatorics

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.

## Polyhedral combinatorics :proceeding of a DIMACS Workshop#June 12-16 Cook, William ; Seymour, Paul D. | American Mathematical Society 1990

Congrès

- 288 p.
ISBN 978-0-8218-6591-0

DIMACS series in discrete mathematics and theoretical computer science , 0001

Localisation : Collection 1er étage

chemin et cycle # combinatoire polyèdrale # graphe eulérien et hamiltonien # problème du facteur chinois # problème du voyageur de commerce # programmation combinatoire # programmation entière

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

## Graph structure theory :proceedings of the AMS-IMS-SIAM joint summer research conference on graph minors at the University of Washington#June 22 to July 5 Robertson, Neil ; Seymour, Paul D. | American Mathematical Society 1993

Congrès

- 688 p.
ISBN 978-0-8218-5160-9

Contemporary mathematics , 0147

Localisation : Collection 1er étage

2-polymatroïde # adaptation parfaite # arbre disjoint # automate fini # base de Hilbert des circuits # conjecture de Las Vergnas et Meyniel # cycle non contractible court # demi-grille infinie # digraphe intercyclique # fonction dominante # grammaire de graphes # graphe H-libre # graphe plan # graphe plongé # invariant de Tutte # invariant de graphe # logique du second ordre monadique # matroïde extrême # mineur de graphes topologique # mineur induit # noeud et tresse # nombre achromatique # plan projectif # plongement sans liens # polynôme de type Jones # théorie de structure de graphe # théorie des graphes topologique # théorème de couverture de cycle # traînée eulérienne # triangulation de surface # troncature calculable sous exponentiellement 2-polymatroïde # adaptation parfaite # arbre disjoint # automate fini # base de Hilbert des circuits # conjecture de Las Vergnas et Meyniel # cycle non contractible court # demi-grille infinie # digraphe intercyclique # fonction dominante # grammaire de graphes # graphe H-libre # graphe plan # graphe plongé # invariant de Tutte # invariant de graphe # logique du second ordre monadique # matroïde extrême # mineur de graphes topologique # mineur ...

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

## Excluding infinite clique minors Robertson, Neil ; Seymour, Paul D. ; Thomas , Robin | American Mathematical Society 1995

Ouvrage

ISBN 978-0-8218-0402-5

Memoirs of the american mathematical society , 0566

Localisation : Collection 1er étage

arbre topologique # arbre-décomposition # dissection limitée # division longue # division robuste # décomposition d'arbre bien fondée # exclusion de K indice aleph indice 0 # exclusion de demi- grille # exclusion de mineur de clique infini # graphe complet # graphe infini # havre et mineur # havres rassemblés en groupes d'ordre aleph indice 0 # moitié facile

#### Filtrer

##### Langue

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

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z