Total coloring

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ′′(G) of a graph G is the fewest colors needed in any total coloring of G. The total graph T = T(G) of a graph G is a graph such that (i) the vertex set of T corresponds to the vertices and edges of G and (ii) two vertices are adjacent in T if and only if their corresponding elements are either adjacent or incident in G. Then total coloring of G becomes a (proper) vertex coloring of T(G). A total coloring is a partitioning of the vertices and edges of the graph into total independent sets. Some inequalities for χ′′(G): χ′′(G) ≥ Δ(G) + 1. χ′′(G) ≤ Δ(G) + 1026. (Molloy, Reed 1998) χ′′(G) ≤ Δ(G) + 8 ln8(Δ(G)) for sufficiently large Δ(G). (Hind, Molloy, Reed 1998) χ′′(G) ≤ ch′(G) + 2. Here Δ(G) is the maximum degree; and ch′(G), the edge choosability. Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. The next step is to look for any Brooks-typed or Vizing-typed upper bound on the total chromatic number in terms of maximum degree. The total coloring version of maximum degree upper bound is a difficult problem that has eluded mathematicians for 50 years. A trivial lower bound for χ′′(G) is Δ(G) + 1. Some graphs such as cycles of length and complete bipartite graphs of the form need Δ(G) + 2 colors but no graph has been found that requires more colors. This leads to the speculation that every graph needs either Δ(G) + 1 or Δ(G) + 2 colors, but never more: Total coloring conjecture (Behzad, Vizing). Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by Behzad and Vizing in numerous occasions between 1964 and 1968 (see Jensen & Toft).

À 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.

Concepts associés (9)

Cours associés (6)

Séances de cours associées (44)

Total coloring

List edge-coloring

In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color. A graph G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring.

Théorème de Vizing

Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing. 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. On note χ′(G) le nombre minimum de couleur nécessaire pour avoir une coloration des arêtes.

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

COM-516: Markov chains and algorithmic applications

The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some appl

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practi

Modèles graphiques : Distribution de probabilités conjointes PHYS-512: Statistical physics of computation

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

Coloration graphique II PHYS-642: Statistical physics for optimization & learning

Explore les concepts avancés de coloration graphique, y compris la coloration plantée, le seuil de rigidité, et les variables gelées en points fixes BP.

Programmation dynamique : nombres de Fibonacci

Explore la programmation dynamique avec des nombres de Fibonacci, des algorithmes gourmands de changement de pièce, la coloration graphique et des variantes de knapsack.