NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous w...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Soulignac, F.J., Sueiro, G.
Formato:	JOUR
Materias:	Computational complexity Coordinated graph recognition NP-complete problems {gem, C 4, odd hole}-free graphs
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_02545330_v169_n1_p17_Soulignac
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_02545330_v169_n1_p17_Soulignac
record_format	dspace
spelling	todo:paper_02545330_v169_n1_p17_Soulignac2023-10-03T15:11:34Z NP-hardness of the recognition of coordinated graphs Soulignac, F.J. Sueiro, G. Computational complexity Coordinated graph recognition NP-complete problems {gem, C 4, odd hole}-free graphs A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C 4, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. © 2008 Springer Science+Business Media, LLC. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_02545330_v169_n1_p17_Soulignac
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Computational complexity Coordinated graph recognition NP-complete problems {gem, C 4, odd hole}-free graphs
spellingShingle	Computational complexity Coordinated graph recognition NP-complete problems {gem, C 4, odd hole}-free graphs Soulignac, F.J. Sueiro, G. NP-hardness of the recognition of coordinated graphs
topic_facet	Computational complexity Coordinated graph recognition NP-complete problems {gem, C 4, odd hole}-free graphs
description	A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C 4, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. © 2008 Springer Science+Business Media, LLC.
format	JOUR
author	Soulignac, F.J. Sueiro, G.
author_facet	Soulignac, F.J. Sueiro, G.
author_sort	Soulignac, F.J.
title	NP-hardness of the recognition of coordinated graphs
title_short	NP-hardness of the recognition of coordinated graphs
title_full	NP-hardness of the recognition of coordinated graphs
title_fullStr	NP-hardness of the recognition of coordinated graphs
title_full_unstemmed	NP-hardness of the recognition of coordinated graphs
title_sort	np-hardness of the recognition of coordinated graphs
url	http://hdl.handle.net/20.500.12110/paper_02545330_v169_n1_p17_Soulignac
work_keys_str_mv	AT soulignacfj nphardnessoftherecognitionofcoordinatedgraphs AT sueirog nphardnessoftherecognitionofcoordinatedgraphs
_version_	1807321097317646336

NP-hardness of the recognition of coordinated graphs

Ejemplares similares