Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1889
Tipo: Relatório
Título: Partitioning chordal graphs into independent sets and cliques
Autor(es)/Inventor(es): Hell, Pavol
Klein, Sulamita
Nogueira, Loana Tito
Protti, Fábio
Resumo : We consider the following generalization of split graphs: A graph is said to be a (k,ℓ)-graph if its vertex set can be partitioned into k independent sets and ℓ cliques. (Split graphs are obtained by setting k=ℓ=1.) Much of the appeal of split graphs is due to the fact that they are chordal, a property not shared by (k,ℓ)-graphs in general. (For instance, being a (k,0)-graph is equivalent to being k-colourable.) However, if we keep the assumption of chordality, nice algorithms and characterization theorems are possible. Indeed, our main result is a forbidden subgraph characterization of chordal (k,ℓ)-graphs. We also give an O(n(m+n)) recognition algorithm for chordal (k,ℓ)-graphs. When k=1, our algorithm runs in time O(m+n). In particular, we obtain a new simple and efficient greedy algorithm for the recognition of split graphs, from which it is easy to derive the well known forbidden subgraph characterization of split graphs. The algorithm and the characterization extend, in a natural way, to the ‘list’ (or ‘pre-colouring extension’) version of the split partition problem — given a graph with some vertices pre-assigned to the independent set, or to the clique, is there a split partition extending this pre-assignment? Another way to think of our main result is the following min-max property of chordal graphs: the maximum number of independent (i.e., disjoint and nonadjacent) Kr's equals the minimum number of cliques that meet all Kr's.
Palavras-chave: Chordal graphs
Split graphs
Greedy algorithms
List partitions
Min-max theorems
Grafos cordal
Grafos clique
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0501
Data de publicação: 31-Dez-2001
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: HELL, P. et al. Partitioning chordal graphs into independent sets and cliques. Rio de Janeiro: NCE/UFRJ, 2001. (Relatório Técnico, 05/01)
URI: http://hdl.handle.net/11422/1889
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
05_01_000613094.pdf726,43 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.