Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Language: English

You searched for subject:(Nombre b chromatique). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Mortada, Maidoun. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.

Degree: Docteur es, Informatique, 2013, Université Claude Bernard – Lyon I

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance

Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions…

Advisors/Committee Members: Kheddouci, Hamamache (thesis director).

Subjects/Keywords: Coloration de graphe; B-coloration; Nombre b-chromatique; Graphe régulier; Emballage de graphe; Emballage marqué de graphe; Graphe puissance; Arbre non-étoile; Graph coloring; B-coloring; B-chromatic number; Regular graph; Graph packing; Labeled packing of graph; Power graph; Non-star tree; 004.0151

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Mortada, M. (2013). The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. (Doctoral Dissertation). Université Claude Bernard – Lyon I. Retrieved from http://www.theses.fr/2013LYO10116

Chicago Manual of Style (16th Edition):

Mortada, Maidoun. “The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.” 2013. Doctoral Dissertation, Université Claude Bernard – Lyon I. Accessed September 23, 2020. http://www.theses.fr/2013LYO10116.

MLA Handbook (7th Edition):

Mortada, Maidoun. “The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.” 2013. Web. 23 Sep 2020.

Vancouver:

Mortada M. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. [Internet] [Doctoral dissertation]. Université Claude Bernard – Lyon I; 2013. [cited 2020 Sep 23]. Available from: http://www.theses.fr/2013LYO10116.

Council of Science Editors:

Mortada M. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. [Doctoral Dissertation]. Université Claude Bernard – Lyon I; 2013. Available from: http://www.theses.fr/2013LYO10116

.