Polytope des independants d'un graphe serie-parallele

A graph is said to be serie-parallel if it doesn't contain an homeomorph to K₄. The aim of the paper is the demonstration of Chvatal's conjecture on the polytope of independent set of vertices in such graphs. This is done classically by using LP-duality, the algorithm for constructing the primal-dual solution having the nice property to be linear in the number of vertices.     

Hypergraphes de chaines d'aretes d'un arbre

We introduce the ‘edges-paths hypergraph of a tree’ and study relations of this notion with graphic geometries, chordable graphs. As particular case, we give a simple characterization of intervals hypergraphs.     

Nombre chromatique total d'un hypergraphe

In this paper, the author defines a hypergraph total chromatic number and determines this number for the complete h-partite and for the complete h-uniform hypergraphs.     

Arbres minimaux d'un graphe preordonne

We study the minimal spanning trees of a connected graph G = (X,U) where U is partially preordered (or quasi-ordered). We characterize several kinds of optimal spanning trees and give conditions for existence of strongly optimal trees. Generalizations to bases of matroids (binary matroïds in part 2) are immediate. Sone of our results are given in terms of Krugdahl's dependence graphs. They imply previous results of Rosenstiehl and Gale in the case of linear orders or preorders.     

Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente

In this article we prove that a sufficient condition for an oriented strongly connected graph with n vertices to be Hamiltonian is: (1) for any two nonadjacent vertices x and y

$\text{d}{}^{\mathrm{+}}\text{(x)+d}{}^{\mathrm{?}}\text{(x)+d}{}^{\mathrm{+}}\text{(y)+d}{}^{\mathrm{?}}\text{(y)?sn?1}$

.     

Parité des cycles contenant des sommets specifiés d'un graphe

It is shown that, if G is a h-connected non bipartite graph, then given h ? 1 vertices of G, there is an odd elementary cycle containing then. The theorem is also true for even cycles.     

La reduction minimale d'un graphe a une reunion de cliques

On obtient la valeur maximale de l'indice de réduction minimale d'un graphe á une réunion de k cliques.     

Sur les arborescences dans un graphe oriente

The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d⁺_G(x)+d^?_G(x)+d^?_G(y)+d^?_G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved.     

Les 5-colorations d'un graphe planaire forment une classe de commutation unique

There is one class of interchanges for the 5-colorations of a planer graph. As a consequence it is always possible to reach a four coloration (if it exists) by a sequence of interchange from any 5-coloration. A theorem is given for surfaces of genus g.     

Un probleme de partition de l'ensemble des parties a trois elements d'un ensemble fini

Let X be a set of n elements. Let $\text{T}$₃(X) be the set of all triples of X. We define a clique as a set of triples which intersect pairwise in two elements. In this paper we prove that if n?6, the minimum cardinality of a partition of $\text{T}$₃(X) into cliques is $\text{[}\text{1}\text{4}\text{(n?1)}{}^2\text{]}$.     

Graphes cubiques d'indice trois,graphes cubiques isochromatiques,graphes cubiques d'indice quatre

The process introduced by E. Johnson [Amer. Math. Monthly73 (1966), 52–55] for constructing connected cubic graphs can be modified so as to obtain restricted classes of cubic graphs, in particular, those defined by their chromatic number or their chromatic index. We construct here the graphs of chromatic number three and the graphs whose chromatic number is equal to its chromatic index (isochromatic graphs). We then give results about the construction of the class of graphs of chromatic index four, and in particular, we construct an infinite class of “snarks.”     

Sur l'histoire des démonstrations analytiques du théorème fondamental de l'algèbre

The first proof of the fundamental theorem of algebra, proposed by D'Alembert in 1746 and practically unknown to this day, stimulated a series of “analytic” proofs which made essential use of the properties of polynomials as analytic functions and placed the theorem within complex analysis. One of the simplest and most widely known modern proofs is formed from the “analytic” proofs of Gauss, Argand, Legendre and Cauchy, which used and developed the ideas of D'Alembert.     

Sur l'étude directe d'equations non linéaires intervenant en théorie du contrôle optimal

Some equivalent properties of the existence of Fréchet smooth norms in weakly compactly generated (WCG) Banach spaces are shown. Heredity of WCG property in such spaces is proved. The property of having a shrinking Marku?evi? basis is hereditary in all Banach spaces. Projections in WCG spaces and their duals are studied.     

Sur les extensions lineaires d'une famille particuliere d'ordres partiels

Corners are defined as ideals of an ordered integer half-dihedron; the paper develops a method of enumeration of the linear extensions of a given corner by means of an alternating sum of products of trinomials. The main result substantially generalizes previously known results and is by itself the starting point of generalizations to some further ordered sets.     

Sur les décompositions directes des contractions de l'espace de Hilbert

Soit H un espace de Hilbert séparable, T ∈ $\text{B}$(H) une contraction complètement nonunitaire et H₁ ? H un sous-espace fermé, invariant à T. Le but de cette Note est de trouver une condition nécessaire et suffisante pour qu'il existe un sous-espace fermé H′ ? H, invariant à T et tel que l'espace H se décompose en somme directe $\text{H = H′ ? H}{}_1$ pas nécessairement orthogonale.     

Le degré minimal du groupe d'un code bipréfixe fini

Some finite sets of words, the so-called biprefix codes, are known to be associated with some transitive groups. We show here that if n is the degree of the group and d its minimal degree, the difference n — d tends to infinity with n.