Un graphe est -choosable (également appelé -list-colorable ) si, pour toute fonction qui mappe des sommets sur des ensembles de couleurs, il existe une affectation de couleur telle que, pour tous les sommets , , et tel que, pour tous les , .k f k c v c ( v ) ∈ f ( v ) v w c ( v ) ≠ c ( w...
Le théorème des quatre couleurs (4CT) stipule que chaque graphe planaire peut être coloré en quatre. [Appel, Haken 1976] et [Robertson, Sanders, Seymour, Thomas 1997] ont donné deux preuves. Ces deux preuves sont assistées par ordinateur et assez intimidantes. Il existe plusieurs conjectures en...
Mise à jour : L'ensemble des obstructions (c'est-à-dire la "barrière" NxM entre les tailles de grille colorables et non colorables) pour toutes les couleurs 4 monochromes sans rectangle est maintenant connu . Quelqu'un veut-il essayer 5 couleurs? ;) La question suivante découle de la théorie de...
Supposons que est un graphique avec un nombre à colorier d = χ ( G ) . Considérez le jeu suivant entre Alice et Bob. À chaque tour, Alice choisit un sommet et Bob répond avec une couleur en { 1 , … , d - 1 } pour ce sommet. Le jeu se termine lorsqu'un bord monochromatique est découvert. Soit X ( G...
Supposons que nous relâchions le problème du comptage des colorations appropriées en comptant les colorations pondérées comme suit: chaque coloration appropriée obtient le poids 1 et chaque coloration incorrecte obtient le poids où est une constante et est le nombre d'arêtes dont les extrémités...
Pour A⊂[n]A⊂[n]A\subset [n] On note aiaia_i la ithithi^{th} plus petit élément de AAA . Pour deux ensembles d'éléments kkk , A,B⊂[n]A,B⊂[n]A,B\subset [n] , nous disons que A≤BA≤BA\le B si ai≤biai≤bia_i\le b_i pour chaque iii . A kkk -uniform hypergraphe H⊂[n]H⊂[n]{\mathcal H}\subset [n] est appelée...
Considérons l'ensemble des graphes planaires où toutes les faces internes sont des triangles. S'il y a un point intérieur de degré impair, le graphique ne peut pas être tricolore. Si chaque point intérieur a un degré égal, peut-il toujours être tricolore? Idéalement, je voudrais un petit...
En raisonnant un peu sur cette question , j'ai essayé d'identifier toutes les différentes raisons pour lesquelles un graphe peut ne pas être k colorable. Ce sont les 2 seules raisons que j'ai pu identifier jusqu'à présent:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk contient une clique de taille k + 1 ....
Le problème que nous considérons ici est l'extension du problème bien connu de coloration d'intervalle. Au lieu d'intervalles, nous considérons des rectangles ayant des côtés parallèles aux axes. L'objectif est de colorer les rectangles en utilisant un nombre minimum de couleurs de sorte que deux...
Récemment, j'ai rencontré la variante suivante de coloration des bords. Étant donné un graphe connexe non orienté, trouvez une coloration des arêtes qui utilise le nombre maximal de couleurs tout en satisfaisant également la contrainte selon laquelle, pour chaque sommet , les arêtes incidentes à...
Désolé, si c'est une question naïve, mais je n'ai trouvé la justification dans aucun des principaux manuels comme Bondy-Murty, Diestel ou West. Les graphiques parfaits ont de nombreuses propriétés magnifiques, mais quelle est la seule raison pour laquelle ils sont appelés parfaits? Ou est-ce juste...
La coloration à 3 arêtes des graphiques cubiques est complète. Le théorème à quatre couleurs équivaut à «Chaque graphique cubique sans pont plan est colorable sur 3 bords».NPNPNP Quelle est la complexité de la coloration à 3 arêtes des graphiques planaires cubiques? De plus, il est conjecturé que...
Les problèmes de coloration des graphiques sont déjà assez difficiles pour la plupart des gens . Malgré cela, je vais devoir être difficile et poser un problème sur la coloration hypergraphique. Question. Quels sont les algorithmes efficaces pour trouver une coloration des bords approximativement...
Dans l'article "Sur la complexité de certains jeux de coloriage", Bodlaender pose quelques questions ouvertes sur la complexité de décider si le joueur 1 ou 2 a une stratégie gagnante dans certains jeux de coloriage de graphiques. Est-ce que quelqu'un sait s'ils ont été résolus? 1) Dans une partie,...
Je cherche un petit graphe GGG dont le nombre chromatique vectoriel est plus petit que le nombre chromatique,
Je recherche des résultats de dureté sur la coloration des sommets des graphiques à degré borné. Étant donné un graphique , nous savons que pour tout ϵ > 0 , il est difficile d'approximer χ ( G ) dans un facteur de | V | 1 - ϵ sauf si NP = ZPP [ 1 ]. Mais que se passe-t-il si le degré maximal de...
Dans mon travail, le problème suivant se pose: Existe-t-il un algorithme connu, qui se rapproche du nombre chromatique d'un graphique sans un ensemble indépendant d'ordre 65? (Donc alpha (G) <= 64 est connu et | V | / 64 est une borne inférieure triviale, | V | une borne supérieure triviale....
Relâchons un peu la coloration, c'est-à-dire que nous permettons à un petit nombre de sommets adjacents de se voir attribuer la même couleur. Un composant monochromatique est défini comme étant un composant connecté dans le sous-graphique induit par l'ensemble de sommets qui reçoivent la même...
La revendication suivante est-elle connue? Affirmation : Pour tout graphe à n sommets, il existe une coloration de G telle que chaque ensemble indépendant soit coloré par au plus O ( √gGGnnngGGcouleurs.O (
Est-il difficile d'approcher le nombre chromatique fractionnaire sur des graphiques de degrés