Automorphismes des algèbres cubiques

Manin associated to a quadratic algebra (quantum space) the quantum matrix group of its automorphisms. This Note aims to demonstrate that Manin's construction can be extended for quantum spaces which are non-quadratic homogeneous algebras. The Artin–Schelter classification of regular algebras of global dimension three contains two types of algebra: quadratic and cubic. Ewen and Ogievetsky classified the quantum matrix groups which are deformations of GL(3) corresponding to the quadratic algebras in the Artin–Schelter classification. In this Note we consider the cubic Artin–Schelter algebras as quantum spaces and construct Hopf algebras of their automorphisms. To cite this article: T. Popov, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Even polyhedral decompositions of cubic graphs

An even polyhedral decomposition of a finite cubic graph G is defined as a set of elementary cycles of even length in G with the property that each edge of G lies in exactly two of them. If G has chromatic index three, then G has an even polyhedral decomposition. We show that, contrary to a theorem of Szekkeres [2], this property to have an even polyhedral decomposition doesn't characterize the cubic graphs of chromatic index three. In particular, there exists an infinite family of sharks all having an even polyhedral decomposition.     

Chromatic Polynomials of Complements of Bipartite Graphs

We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root.     

Algèbres de Hopf de graphes

We define graded Hopf algebras with bases labeled by various types of graphs and hypergraphs, provided with natural embeddings into an algebra of polynomials in infinitely many variables. These algebras are graded by the number of edges and can be considered as generalizations of symmetric or quasi-symmetric functions. To cite this article: J.-C. Novelli et al., C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

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.     

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs. We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K_{⌈t/2⌉,⌊t/2⌋} in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases. As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. * Research partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321. † Research partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

On directed local chromatic number,shift graphs,and Borsuk‐like graphs

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010     

Isomorphismes d'hypergraphes par intersections équicardinales d'arêtes et configurations exclues

In this note we characterize isomorphism between two hypergraphs by means of equicardinality of certain edge intersections and the exclusion of certain pairs of subhypergraphs. Our result is slightly stronger than Theorem 3 of C. Berge and R. Rado (J. Combinatorial Theory Ser. B13 (1972), 226–241) in particular in that isolated vertices are admitted. As a corollary we obtain a result due to J.-L. Paillet.     

Coloring intersection graphs of x-monotone curves in the plane

A class of graphs G is χ-bounded if the chromatic number of the graphs in G is bounded by some function of their clique number. We show that the class of intersection graphs of simple families of x-monotone curves in the plane intersecting a vertical line is χ-bounded. As a corollary, we show that the class of intersection graphs of rays in the plane is χ-bounded, and the class of intersection graphs of unit segments in the plane is χ-bounded.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Hajós' graph-coloring conjecture: Variations and counterexamples

For each integer n ≥ 7, we exhibit graphs of chromatic number n that contain no subdivided K_n as a subgraph. However, we show that a graph with chromatic number 4 contains as a subgraph a subdivided K₄ in which each triangle of the K₄ is subdivided to form an odd cycle.     

Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.     

Homologies d'algèbres Artin–Schelter régulières cubiques

Hochschild homology of cubic Artin–Schelter regular algebras of type A with generic coefficients is computed. We follow the method used by Van den Bergh (K-Theory 8 (1994) 213–230) in the quadratic case, by considering these algebras as deformations of a polynomial algebra, with remarkable Poisson brackets. A new quasi-isomorphism is introduced. De Rham cohomology, cyclic and periodic cyclic homologies, and Hochschild cohomology are also computed. To cite this article: N. Marconnet, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Sur le joint d'une famille de graphes

Les graphes envisagés dans cet article sont non orientés, sans boucles ni arês multiples. On désigne par X(G) et E(G) les ensembles de sommets et d'arêtes d'un graphe G; ces ensembles seront toujours finis. Les notations usuelles sont ceiles de Berge [1].Dans [5], Zykov introduit la notion de graphe joint de deux graphes donnés. Une propriété du joint de deux graphes dont l'un est réduit à un sommet est donnée dans [3]; c'est une étude plus générate et systématique que nous présentons ici.     

Le probleme d'etoiles pour graphes est np-complet

Nous appelons problème de ‘recollement de voisinages’ (RV) (‘star problem’ ou ‘problème d'ètoiles’) le problème qui consiste à savoir, étant donnée une famille $\text{V}$ de parties d'un ensemble S, s'il existe un graphe (non orienté et sans boucle) dont la famille de voisinages coïncide avec $\text{V}$. L'objectif de cet article est de montrer que le problème RV est NP-complet. La preuve s'appuiera sur l'èquivalence entre RV et le probléme de trouver un automorphisme d'ordre 2 dans un graphe quelconque (AUT2). La NP-complétude de AUT2 a été démontrée par Anna Lubiw [5].     

A new approach on estimation of the tail indexUne nouvelle méthode pour l'estimation de l'index d'une queue

A new approach on tail index estimation is proposed based on studying the in-sample evolution of appropriately chosen diverging statistics. The resulting estimators are simple to construct, and they can be generalized to address other rate estimation problems as well. To cite this article: D.N. Politis, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 279–282.     

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.