Sobre a complexidade de coloração mista

Description

Grafos mistos são estruturas matemáticas que mesclam características de grafos direcionados e não-direcionados. Formalmente, um grafo misto pode ser definido por uma tripla GM = (V, A, E), onde V , A e E representam, respectivamente, um conjunto de vértices, de arcos e de arestas. Uma k-coloração mista de GM = (V, A, E) é função c : V → {0, . . . , k − 1} tal que c(u) < c(v), se (u, v) ∈ A, e c(u) = c(v), se [u, v] ∈ E. O problema de Coloração Mista consiste em determinar o número cromático misto de GM , denotado por χM (GM ), que é o menor inteiro k tal que GM admite uma k-coloração mista. Esse problema modela variações de problemas de escalonamento que consideram simultaneamente restrições de precedência e de compartilhamento de recursos. Neste trabalho, mostramos que Coloração Mista é N P -difícil para as classes dos grafos cordais, dos grafos linha de grafos bipartidos e dos grafos linha de grafos periplanares.

Abstract

National audience

Additional details