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:

You searched for subject:(Connected greedy coloring). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Le, Ngoc Khang. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.

Degree: Docteur es, Informatique, 2018, Lyon

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits.

Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the…

Advisors/Committee Members: Trotignon, Nicolas (thesis director).

Subjects/Keywords: Coloration de graphe; Reconnaissance de graphe; Sous-graphes induits; Graphes sans ISK4; Graphes sans trou pair; Coloration gloutonne connexe; Graph coloring; Graph recognition; Induced subgraphs; ISK4-free graphs; Even-hole-free graphs; Connected greedy coloring

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Le, N. K. (2018). Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. (Doctoral Dissertation). Lyon. Retrieved from http://www.theses.fr/2018LYSEN021

Chicago Manual of Style (16th Edition):

Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Doctoral Dissertation, Lyon. Accessed January 19, 2021. http://www.theses.fr/2018LYSEN021.

MLA Handbook (7th Edition):

Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Web. 19 Jan 2021.

Vancouver:

Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Internet] [Doctoral dissertation]. Lyon; 2018. [cited 2021 Jan 19]. Available from: http://www.theses.fr/2018LYSEN021.

Council of Science Editors:

Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Doctoral Dissertation]. Lyon; 2018. Available from: http://www.theses.fr/2018LYSEN021

.