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:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(B chromatic number). Showing records 1 – 3 of 3 total matches.

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 August 04, 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. 04 Aug 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 Aug 04]. 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

2. Premzl, Mojca. b-barvanja regularnih grafov in grafovskih produktov.

Degree: 2016, Univerza v Mariboru

Dobro barvanje vozlišč grafa G, v katerem v vsakem barvnem razredu obstaja vsaj eno tako vozlišče, ki ima vsaj enega soseda v vsakem drugem barvnem razredu, je b-barvanje grafa G. Največje naravno število k, za katerega graf premore b-barvanje s k različnimi barvami, imenujemo b-kromatično število grafa in ga označimo s varphi(G). V magistrskem delu bomo predstavili definicijo b-barvanja in podali natančne vrednosti b-kromatičnega števila za poti, cikle, polne grafe, neodvisne množice in polne dvodelne grafe. Dokazali bomo, da je določanje b-kromatičnega števila NP-poln problem, kar ima za posledico dejstvo, da lahko b-kromatično število natančno določimo le nekaterim družinam grafov. Že iz same definicije b-barvanja sledi, da je χ(G) leq varphi(G) leq Delta(G)+1. Podali bomo še nekaj zgornjih mej b-kromatičnega števila, ki veljajo za poljubne grafe. Med njimi izpostavimo predvsem m-stopnjo grafa m(G)

to je največje tako število m, za katerega graf G vsebuje vsaj m vozlišč stopnje vsaj m-1. Natančno vrednost b-kromatičnega števila lahko med drugim določimo tudi poljubnemu drevesu, in to v polinomskem času. V poglavju o regularnih grafih bomo obravnavali predvsem pogoje, ki jim mora zadoščati d-regularen graf, da bo njegovo b-kromatično število enako zgornji meji, to je d+1. Eden izmed pogojev je, da ima graf zadostno število vozlišč, in sicer vsaj 2d3. Dokazali bomo tudi, da je v d-regularnem grafu varphi(G)=d+1, če je ožina grafa g(G) geq 6 oz. če je g(G)geq 5 in graf bodisi ne vsebuje nobenega cikla dolžine 6 bodisi je d leq 6. Nekateri d-regularni grafi lahko imajo kljub velikemu d majhno b-kromatično število (npr. dvodelni graf Kd,d). Dokazali bomo, da velikost b-kromatičnega števila d-regularnih grafov, ki ne vsebujejo nobenega 4-cikla, linearno narašča z velikostjo d. Za regularne grafe, ki ne vsebujejo nobenega 4-cikla in imajo mathrm{diam}(G) geq 6, prav tako velja, da je varphi(G)=d+1. Enako velja tudi za vse regularne grafe, ki ne vsebujejo nobenega 4-cikla, njihova vozliščna povezanost pa je κ(G) leq frac{d+1}{2}. Nazadnje bomo dokazali še, da obstajajo le štirje kubični grafi, za katere je varphi(G) leq d, eden izmed njih je Petersenov graf. V zadnjem poglavju bomo obravnavali b-barvanja grafovskih produktov, in sicer kartezičnega, krepkega, leksikografskega in direktnega. V primeru kartezičnega in direktnega produkta je b-kromatično število navzdol omejeno z max left{varphi(G), varphi(H) right}, v primeru krepkega in leksikografskega produkta pa je spodnja meja enaka varphi(G) cdot varphi(H). Za vsak produkt posebej bomo podali še zgornjo mejo b-kromatičnega števila. Določili bomo še nekatere natančne vrednosti b-kromatičnega števila grafovskih produktov, pri čemer bodo posamezni faktorji enaki potem, ciklom, zvezdam, v nekaterih primerih pa bo eden izmed faktorjev celo poljuben graf.

A b-coloring of a graph G is a proper coloring of its vertices such that every color class contains a vertex that has a neighbor in…

Advisors/Committee Members: Jakovac, Marko.

Subjects/Keywords: b-barvanje; b-kromatično število; NP-poln problem; regularni graf,kartezični produkt; krepki produkt; leksikografski produkt; direktni produkt.; b-coloring; b-chromatic number; NP-complete problem; regular graph,Cartesian product; strong product; lexicographic product; direct product.; info:eu-repo/classification/udc/519.174(043.2)

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Premzl, M. (2016). b-barvanja regularnih grafov in grafovskih produktov. (Masters Thesis). Univerza v Mariboru. Retrieved from https://dk.um.si/IzpisGradiva.php?id=62028 ; https://dk.um.si/Dokument.php?id=105499&dn= ; https://plus.si.cobiss.net/opac7/bib/22663432?lang=sl

Chicago Manual of Style (16th Edition):

Premzl, Mojca. “b-barvanja regularnih grafov in grafovskih produktov.” 2016. Masters Thesis, Univerza v Mariboru. Accessed August 04, 2020. https://dk.um.si/IzpisGradiva.php?id=62028 ; https://dk.um.si/Dokument.php?id=105499&dn= ; https://plus.si.cobiss.net/opac7/bib/22663432?lang=sl.

MLA Handbook (7th Edition):

Premzl, Mojca. “b-barvanja regularnih grafov in grafovskih produktov.” 2016. Web. 04 Aug 2020.

Vancouver:

Premzl M. b-barvanja regularnih grafov in grafovskih produktov. [Internet] [Masters thesis]. Univerza v Mariboru; 2016. [cited 2020 Aug 04]. Available from: https://dk.um.si/IzpisGradiva.php?id=62028 ; https://dk.um.si/Dokument.php?id=105499&dn= ; https://plus.si.cobiss.net/opac7/bib/22663432?lang=sl.

Council of Science Editors:

Premzl M. b-barvanja regularnih grafov in grafovskih produktov. [Masters Thesis]. Univerza v Mariboru; 2016. Available from: https://dk.um.si/IzpisGradiva.php?id=62028 ; https://dk.um.si/Dokument.php?id=105499&dn= ; https://plus.si.cobiss.net/opac7/bib/22663432?lang=sl

3. Jakovac, Marko. Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija.

Degree: 2011, Univerza v Mariboru

Subjects/Keywords: graf Sierpińskega; graf trikotnikov Sierpińskega; regularni graf Sierpińskega; posplošeni graf trikotnikov Sierpińskega; kromatično število; kromatični indeks; celotno kromatično število; b-kromatično število; Petersenov graf; regularni graf; ožina; premer; krepki produkt; leksikografski produkt; direktni produkt; pot; cikel; zvezda; polni dvodelni graf; disertacije; Sierpiński graph; Sierpiński gasket graph; regular Sierpiński graph; generalized gasket graph; chromatic number; chromatic index; total chromatic number; Petersen graph; regular graph; girth; diameter; strong product; lexicographic product; direct product; path; cycle; star; complete bipartite graph; info:eu-repo/classification/udc/519.174(043.3)

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Jakovac, M. (2011). Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija. (Doctoral Dissertation). Univerza v Mariboru. Retrieved from https://dk.um.si/IzpisGradiva.php?id=20011 ; https://dk.um.si/Dokument.php?id=24532&dn= ; https://plus.si.cobiss.net/opac7/bib/253571072?lang=sl

Chicago Manual of Style (16th Edition):

Jakovac, Marko. “Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija.” 2011. Doctoral Dissertation, Univerza v Mariboru. Accessed August 04, 2020. https://dk.um.si/IzpisGradiva.php?id=20011 ; https://dk.um.si/Dokument.php?id=24532&dn= ; https://plus.si.cobiss.net/opac7/bib/253571072?lang=sl.

MLA Handbook (7th Edition):

Jakovac, Marko. “Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija.” 2011. Web. 04 Aug 2020.

Vancouver:

Jakovac M. Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija. [Internet] [Doctoral dissertation]. Univerza v Mariboru; 2011. [cited 2020 Aug 04]. Available from: https://dk.um.si/IzpisGradiva.php?id=20011 ; https://dk.um.si/Dokument.php?id=24532&dn= ; https://plus.si.cobiss.net/opac7/bib/253571072?lang=sl.

Council of Science Editors:

Jakovac M. Barvanja grafov Sierpińskega in b-barvanja : doktorska disertacija. [Doctoral Dissertation]. Univerza v Mariboru; 2011. Available from: https://dk.um.si/IzpisGradiva.php?id=20011 ; https://dk.um.si/Dokument.php?id=24532&dn= ; https://plus.si.cobiss.net/opac7/bib/253571072?lang=sl

.