numero cromatico oor Engels

numero cromatico

Vertalings in die woordeboek Italiaans - Engels

chromatic number

naamwoord

smallest number of colours

voorbeelde

Il numero cromatico continua a essere 4.
The chromatic number continues to be 4.

(b) (Stockmeyer [1973]) Decidere se un grafo planare ha un numero cromatico 3.
(b) (Stockmeyer [1973]) Decide whether a given planar graph has chromatic number 3.

In pratica esistono grafi con un numero cromatico arbitrariamente grande che non contengono nessun triangolo K 3 .
Indeed, there are graphs with arbitrarily large chromatic number that contain no K 3 .

Il grado massimo ci dà ancora un upper bound sul numero cromatico: Teorema 16.18.
The maximum degree also gives an upper bound on the chromatic number: Theorem 16.18.

Per definizione, i grafi con numero cromatico al massimo 2 sono precisamente i grafi bipartiti.
By definition, the graphs with chromatic number at most 2 are precisely the bipartite graphs.

Il numero cromatico rimane 4, ma il numero di Betti cambia in 1.
The chromatic number remaii~s4 but the Betti number has changed to 1.

Due altri importanti invarianti topologici di una superficie sono il suo numero cromatico e il numero di Betti.
Two other important topological invariants of a surface are its chromatic number and Betti number.

Un'altra proprietà locale che porta a un numero cromatico elevato è la presenza di una grande cricca.
Another local property that leads to high chromatic number is the presence of a large clique.

Teorema di Mycielski (Zykov (1949), Mycielski (1955)): esistono grafi senza triangoli con numero cromatico arbitrariamente elevato.
Mycielski’s Theorem (Alexander Zykov 1949, Jan Mycielski 1955): There exist triangle-free graphs with arbitrarily high chromatic number.

Dal teorema di Brooks, i grafi con numero cromatico elevato devono avere il grado massimo elevato.
From Brooks’s theorem, graphs with high chromatic number must have high maximum degree.

I grafi con grandi cricche hanno numero cromatico elevato, ma non è vero il contrario.
Graphs with large cliques have a high chromatic number, but the opposite is not true.

Il polinomio cromatico include almeno altrettante informazioni sulla colorabilità di G del numero cromatico.
The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number.

Cosa sorprendente, il numero cromatico è salito a 6.
Surprisingly, the chromatic number has jumped to 6.

Il toro ha due facce, è chiuso (senza bordi) e ha numero cromatico 7 e numero di Betti 2.
The torus is two-sided, closed (no-edged) and has a chromatic number of 7 and a Betti number of 2.

Un grafo perfetto è un grafo nel quale il numero di cricca equivale al numero cromatico in ogni sottografo indotto.
A perfect graph is a graph in which the clique number equals the chromatic number in every induced subgraph.

Ovviamente, se un grafo G contiene una clique di dimensione k, allora il numero cromatico di G è almeno pari a k.
Obviously, if a graph G contains a clique of size k, then the chromatic number of G is at least k.

(König [1916]) Il numero cromatico di arco di un grafo bipartito G è pari al grado massimo di un vertice in G.
(König [1916]) The edge-chromatic number of a bipartite graph G equals the maximum degree of a vertex in G.

Il numero minimo di colori richiesti per colorare un grafo G è chiamato il suo numero cromatico ed è spesso denotato χ(G).
The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G).

Attraverso questo teorema, limiti simili nella teoria dei grafi estremali possono essere dimostrati per qualsiasi sottografo escluso, a seconda del numero cromatico del sottografo.
Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the chromatic number of the subgraph.

La bottiglia di Klein è a una faccia, senza bordi, ha un numero di Betti uguale a 2 e un numero cromatico uguale a 6.
The Klein bottle is one-sided, no-edged and has a Betti number of 2 and a chromatic number of 6.

Un ciclo dispari di lunghezza maggiore di 3 non può essere perfetto, perché il suo numero cromatico e il suo numero di cricca è due.
An odd cycle of length greater than 3 cannot be perfect, because its chromatic number is three and its clique number is two.

La cricca massimale più grande è una cricca massima e, poiché i grafi cordali sono perfetti, la dimensione della cricca è uguale al numero cromatico del grafo cordale.
The largest maximal clique is a maximum clique, and, as chordal graphs are perfect, the size of this clique equals the chromatic number of the chordal graph.

La congettura di Hadwiger, ancora non dimostrata, collega la dimensione della più grande cricca di un minore in un grafo (il suo numero di Hadwiger) al suo numero cromatico.
Hadwiger's conjecture, still unproven, relates the size of the largest clique minor in a graph (its Hadwiger number) to its chromatic number.

I grafi perfetti sono definiti dalle proprietà che il loro numero di cricca uguaglia il loro numero cromatico e che questa uguaglianza vale anche in ciascuno dei loro sottografi indotti.
Perfect graphs are defined by the properties that their clique number equals their chromatic number, and that this equality holds also in each of their induced subgraphs.

In tutti i grafi, il numero di cricca fornisce un limite inferiore per il numero cromatico, in quanto a tutti i vertici di una cricca devono essere assegnati colori distinti in qualsiasi colorazione propria.
In all graphs, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring.