Coloration des arêtes d'un graphe

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs. Mentionnée sans précision supplémentaire, l'expression « coloration des arêtes d'un graphe » désigne le fait d'attribuer à chaque arête une couleur, de sorte que deux arêtes adjacentes (c'est-à-dire ayant une extrémité commune) n'aient jamais la même couleur. (C'est une notion duale de celle de coloration des sommets d'un graphe.) Le nombre minimal de couleurs nécessaire pour réaliser la coloration des arêtes d'un graphe G est appelé indice chromatique de G ou nombre chromatique des arêtes de G et noté χ′(G), ou parfois χ(G). Il ne doit pas être confondu avec le nombre chromatique (des sommets) de G, noté χ(G). Si Δ(G) est le degré maximum de G et μ(G) sa multiplicité (le nombre maximum d'arêtes par paire de sommets), alors : χ′(G) = 1 si et seulement si G est un couplage. χ′(G) ≥ Δ(G). χ′(G) ≤ Δ(G) + 1 (théorème de Vizing). χ′(G) ≤ Δ(G) + μ(G), où G peut être un multigraphe. χ′(G) = Δ(G) dès que G est un graphe biparti (théorème de Kőnig sur les graphes bipartis). χ′(G) = Δ(G) dès que G est un graphe simple planaire tel que Δ(G) ≥ 7 ( section suivante). Comme énoncé ci-dessus, χ′(G) est toujours égal à Δ(G) ou à Δ(G) + 1. G est dit de classe 1 dans le premier cas et de classe 2 dans le second. En 1981, Holyer a prouvé que la détermination de l'appartenance d'un graphe simple à l'une ou l'autre de ces deux classes est un problème NP-complet. Cependant, pour certains cas particuliers, il existe des règles permettant de conclure rapidement.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Personnes associées (2)

Concepts associés (64)

Cours associés (25)

Séances de cours associées (209)

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

MATH-467: Probabilistic methods in combinatorics

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models calle

EPFL2021

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century

IEEE COMPUTER SOC2019

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the

2010

En théorie des graphes, une branche des mathématiques, un graphe cubique est un graphe régulier de degré 3. En d'autres termes, c'est un graphe dans lequel il y a exactement trois arêtes incidentes à chaque sommet. Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non-planaire. Le graphe de Petersen est le plus petit graphe cubique de maille 5. Le graphe de Heawood est le plus petit graphe cubique de maille 6.

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Modèles graphiques : Distribution de probabilités conjointes

Couvre le concept de modèles graphiques et de distributions de probabilités conjointes.

Topologie des surfaces de Riemann

Couvre la topologie des surfaces de Riemann et le concept de triangulation en utilisant un nombre fini de triangles.

Coloriage graphique: bases et applications

Couvre les bases et les applications de la coloration graphique, y compris les vecteurs d'équilibrage et la réalisation d'une équité parfaite.