𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Ensembles d'articulation d'un graphe γ-critique

✍ Scribed by J. Lehel; Zs. Tuza

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
161 KB
Volume
30
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

G) denotes the chromatic number of G. G is 3,-critical (*~: vertex-elitical) if the deletion of any vertex of G gives a (~(G)-l)-chromatic glaph. For A c V(G) c(A) denotes the number of components after the deletion of the vertices of A. G a is the subgraph of G induced by A.

x,~(G A) denotes the number of colorings of G, with at most q colors. We will prove the following results: If G is 3,-critical with T(G)= q' + l, then ('{A)-~ s.~lG.x t for every A ~ V(G). If G. ir not a complete graph and q is large enough then there exists a 3,-critical (3 with "y(G)=q+l which has an articulation set A satisfying G,~(;~ and c(A) = Sq(GA).

Soit Gun graphe 3,-critique avec "y(G)=q + Iet A un ensembk d'articulation de G qui ie coupe en c(A) composantes eonnexes. Nous prouvons ici que c(~.) est lirfit~ par s,~(G ,~, hombre dc colorations du sous-grapl',e G A avec q couleurs au plus ~Th~oreme I).

Soit G o un graphe non-complet quelconque et q un entier arbitraire as,iez grand. Une construction est pr6sent0.e produisant un graphe G qul est 3,~critique avee 3'(G)= q + 1 et ,.lui admet un ensemble d'articulation A tel que G A ~ G. et c(A)= .sq(G A) (Thdor~Sme 2).

📜 SIMILAR VOLUMES

Arbres minimaux d'un graphe preordonne
Arbres minimaux d'un graphe preordonne
✍ Claude Flament; Bruno Leclerc 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 605 KB

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 strongl3,' optimal tress. Generalizations to ba~s of matro'ids (binary matro'ids in par

Sur les quasi-noyaux d'un graphe
Sur les quasi-noyaux d'un graphe
✍ Pierre Duchet; Yahya Ould Hamidoune; Henry Meyniel 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 237 KB

We define three classes of quasi-kernels for a directed graph. As a consequence, we show the existence of quasi-kernels in every progressively finite graph and in every locally finite graph, generalizing the result of Chv~ital and Lov~tsz which deals with the finite case. Our method shows that the p

Permutations representatives d'un graphe
Permutations representatives d'un graphe a seuil
✍ P. Arbouz 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Threshold graphs are known to be permutation graphs. We give, from the describing word of a threshold graph G, a way of getting all representative permutations of G and an explicit counting formula of all these permutations. Rappeb et notations ## Parmi les nombreuses caract6risations des graphes

Une méthode d'énumération des cycles nég
Une méthode d'énumération des cycles négatifs d'un graphe signé
✍ Dragoş-Radu Popescu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 320 KB

## R~sum~ Un graphe sign6 est un graphe non-orient6 ~dont les ar~tes sont positives ou n6gatives. Un sous-graphe quelconque sera nomm6 n6gatif si il contient un nombre impair d'ar~tes n6gatives. Nous avons 6labor6 une m&hode d'6num6ration des sous-graphes n6gatifs d'une famille quelconque des sour

Sur les atomes d'un graphe de Cayley inf
Sur les atomes d'un graphe de Cayley infini
✍ Yahya Ould Hamidoune 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 351 KB

## Let G be an infinite group and let S be a finite subset of G. The outconnectivity of the Cayley graph X=Cay(G, S) is K+(X)=M~~{((FS~\F(:F is a finite nonvoid subset of G). A positive end is a finite subset R such that K+(X) = ((RS)\ RI, which is minimal with respect to this property. We prove t