m

F Nous contacter

0

Documents  05C35 | enregistrements trouvés : 26

O

-A +A

P Q

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

Research talks;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 ...

05C15 ; 05C35 ; 05C85

... Lire [+]

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

- xviii; 562 p.
ISBN 978-3-540-76795-4

Localisation : Colloque 1er étage (BONN)

optimisation # combinatoires # optimisation combinatoire # problème extreme # recherche opérationnelle # analyse mathématique

90Cxx ; 90-06 ; 05-06 ; 90C27 ; 05C35 ; 05C85 ; 00B25

... Lire [+]

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

- vii; 437 p.
ISBN 978-1-107-60109-3

London mathematical society lecture note series , 0392

Localisation : Collection 1er étage

combinatoires # graphe topologique # hypergraphe # graphe aléatoire

05-06 ; 05C10 ; 05C35 ; 05C65 ; 05C80 ; 00B25

... Lire [+]

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

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

Contemporary mathematics , 0531

Localisation : Collection 1er étage

analyse combinatoire # théorie des graphes

05A05 ; 05B05 ; 05B20 ; 05B25 ; 05C15 ; 05C22 ; 05C35 ; 05C50 ; 05D05 ; 05E30 ; 05-06 ; 05Bxx ; 05Cxx ; 00B25 ; 00B30

... Lire [+]

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

- xiv; 370 p.
ISBN 978-0-8218-4380-2

DIMACS series in discrete mathematics and theoretical computer science , 0069

Localisation : Collection 1er étage

combinatoires # informatique # chimie # graphe

68R10 ; 68T05 ; 68T35 ; 05C35 ; 05C30 ; 05C62 ; 05-06 ; 68-06 ; 00B25

... Lire [+]

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

- 413 p.
ISBN 978-963-8022-90-5

Bolyai society mathematical studies , 0007

Localisation : Ouvrage RdC (G)

biologie moléculaire # biomathématique # matrice # optimisation combinatoire # théorie d

05C35 ; 05C50 ; 05Cxx ; 05Dxx

... Lire [+]

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

- 142 p.
ISBN 978-0-8218-6602-3

DIMACS series in discrete mathematics and theoretical computer science , 0010

Localisation : Collection 1er étage

approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # seconde valeur propre et développement linéaire de graphe ré # simulation de chaîne de Markov # échantillonnage uniforme modulo ou groupe de symétrie approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # ...

05-06 ; 05C35 ; 05C80 ; 05C85 ; 60Jxx

... Lire [+]

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

- 152 p.
ISBN 978-0-8218-6600-9

DIMACS series in discrete mathematics and theoretical computer science , 0009

Localisation : Collection 1er étage

algorithme # architecture parallèle # graphe aléatoire # graphe planaire # sphérique # théorie des graphes

05C10 ; 05C35 ; 05C38 ; 05C75 ; 05C85

... Lire [+]

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

Research talks;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.

05C70 ; 05C35 ; 05C15 ; 05C85 ; 68Q25

... Lire [+]

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

Research talks;Combinatorics;Computer Science

A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions. A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for ...

05C85 ; 05C35 ; 68Q25

... Lire [+]

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

- xvi; 335 p.
ISBN 978-1-107-12844-6

Cambridge studies in advanced mathematics , 0149

Localisation : Ouvrage RdC (GODS)

logique mathématique # analyse combinatoire # théorie des intersections

05-02 ; 05D05 ; 05C35

... Lire [+]

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

- xiv; 475 p.
ISBN 978-0-8218-9085-1

American mathematical society colloquium publications , 0060

Localisation : Collection 1er étage

théorie des graphes # algèbre abstraite # isomorphisme # densité # graphe aléatoire # problème extrémale

58J35 ; 58D17 ; 58B25 ; 19L64 ; 81R60 ; 19K56 ; 22E67 ; 32L25 ; 46L80 ; 17B69 ; 05-02 ; 05C80 ; 05C35

... Lire [+]

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

- viii; 144 p.
ISBN 978-0-521-53143-6

London mathematical society student texts , 0055

Localisation : Collection 1er étage

théorie des nombres # combinatoires # somme des carrés # graphe # graphe de Ramanujan # extenseur

11-01 ; 05-01 ; 11E25 ; 11F30 ; 05C25 ; 05C35

... Lire [+]

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

- viii; 235 p.
ISBN 978-0-8218-4691-9

Mathematical surveys and monographs , 0152

Localisation : Collection 1er étage

géométrie combinatoire # algorithme # graphe # problème d'Erdoes # arrangement hyperplan # incidence # suite de Devenport-Schinzel # puzzle

05C35 ; 05C62 ; 52C10 ; 52C30 ; 52C35 ; 52C45 ; 68Q25 ; 68R05 ; 68W05 ; 68W20

... Lire [+]

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

- 115 p.
ISBN 978-3-540-73509-0

Lecture notes in mathematics , 1915

Localisation : Collection 1er étage

combinatoires # graphe # arbre # problème d'extrenum # caractérisation structurelle des graphes # valeurs propres de matrices # domaine nodal # vecteur propre # inégalité de Faber-Krahn # quotient de Rayleight

05C50 ; 05C05 ; 05C35 ; 05C75 ; 15A18 ; 05C22

... Lire [+]

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

- 232 p.
ISBN 978-0-521-83268-7

Cambridge studies in advanced mathematics , 0090

Localisation : Ouvrage RdC (HARP)

optimisation combinatoire # calcul des variations # morphisme # problème isopérimétrique # compression # stabilisation # théorie des graphes # programmation mathématique # problème d'extremium

05-02 ; 05Cxx ; 05C35 ; 90Cxx ; 90-02 ; 90C27 ; 90C35

... Lire [+]

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

- 283 p.
ISBN 978-0-8218-3484-8

Contemporary mathematics , 0342

Localisation : Collection 1er étage

théorie des graphes # représentation de graphes # structure géométrique sur des variétés de faible dimension # optimisation combinatoire # problème d'extremum # algorithme VLSI

05C62 ; 57M50 ; 90C27 ; 05C35 ; 68W35

... Lire [+]

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


ISBN 978-3-540-60717-5

Lecture notes in mathematics , 1623

Localisation : Collection 1er étage

caractérisation structurale des types de graphes # coloriage de graphe # coloriage total # combinatoire # théorie chromatique des graphes # théorie des graphes

05C15 ; 05C35 ; 05C75

... Lire [+]

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

- 142 p.
ISBN 978-1-56881-079-9

Localisation : Ouvrage RdC (CHUN)

Erdös # graphe aléatoire # graphe infini # hypergraphe # nombre chromatique # problème de l'empilement # problème de recouvrement # problème des couleurs # problème extrème # théorie de Ramsey # théorie des graphes # énumération de graphe

05C15 ; 05C30 ; 05C35 ; 05C55 ; 05Cxx

... Lire [+]

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

- 398 p.
ISBN 978-7-03-004772-4

Mathematics and its applications

Localisation : Ouvrage RdC (LIU)

arbre ou espace en graphe # décomposition de graphe # invariant sur noeud # isomorphisme dans les polyèdres # matroïde graphique ou cographique # planarité et graphe planaire # plongeabiliste de réseau # plongeabilité en graphe # plongeabilité rectilinéaire # plongement plan # problème du croisement de Gauss # problème extrémal # surface

05C10 ; 05C35 ; 05Cxx ; 20F22 ; 55Nxx

... Lire [+]

Z