On star and biclique edge-colorings

A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph wit...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Dantas, S., Groshaus, M., Guedes, A., Machado, R.C.S., Ries, B., Sasaki, D.
Formato:	JOUR
Materias:	biclique edge-coloring NP-hard star edge-coloring Coloring Polynomial approximation Set theory Stars Bicliques Chordal bipartite graph Complete bipartite graphs Edge coloring Free graphs Polynomial-time algorithms Two-color Graph theory
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_09696016_v24_n1-2_p339_Dantas
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_09696016_v24_n1-2_p339_Dantas
record_format	dspace
spelling	todo:paper_09696016_v24_n1-2_p339_Dantas2023-10-03T15:55:25Z On star and biclique edge-colorings Dantas, S. Groshaus, M. Guedes, A. Machado, R.C.S. Ries, B. Sasaki, D. biclique edge-coloring NP-hard star edge-coloring Coloring Polynomial approximation Set theory Stars Bicliques Chordal bipartite graph Complete bipartite graphs Edge coloring Free graphs NP-hard Polynomial-time algorithms Two-color Graph theory A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a graph G has a biclique (resp. star) edge-coloring using two colors is NP-hard. Furthermore, we describe polynomial time algorithms for the problem in restricted classes: K3-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles. © 2016 The Authors. International Transactions in Operational Research © 2016 International Federation of Operational Research Societies Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148, USA. Fil:Groshaus, M. 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_09696016_v24_n1-2_p339_Dantas
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	biclique edge-coloring NP-hard star edge-coloring Coloring Polynomial approximation Set theory Stars Bicliques Chordal bipartite graph Complete bipartite graphs Edge coloring Free graphs NP-hard Polynomial-time algorithms Two-color Graph theory
spellingShingle	biclique edge-coloring NP-hard star edge-coloring Coloring Polynomial approximation Set theory Stars Bicliques Chordal bipartite graph Complete bipartite graphs Edge coloring Free graphs NP-hard Polynomial-time algorithms Two-color Graph theory Dantas, S. Groshaus, M. Guedes, A. Machado, R.C.S. Ries, B. Sasaki, D. On star and biclique edge-colorings
topic_facet	biclique edge-coloring NP-hard star edge-coloring Coloring Polynomial approximation Set theory Stars Bicliques Chordal bipartite graph Complete bipartite graphs Edge coloring Free graphs NP-hard Polynomial-time algorithms Two-color Graph theory
description	A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a graph G has a biclique (resp. star) edge-coloring using two colors is NP-hard. Furthermore, we describe polynomial time algorithms for the problem in restricted classes: K3-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles. © 2016 The Authors. International Transactions in Operational Research © 2016 International Federation of Operational Research Societies Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148, USA.
format	JOUR
author	Dantas, S. Groshaus, M. Guedes, A. Machado, R.C.S. Ries, B. Sasaki, D.
author_facet	Dantas, S. Groshaus, M. Guedes, A. Machado, R.C.S. Ries, B. Sasaki, D.
author_sort	Dantas, S.
title	On star and biclique edge-colorings
title_short	On star and biclique edge-colorings
title_full	On star and biclique edge-colorings
title_fullStr	On star and biclique edge-colorings
title_full_unstemmed	On star and biclique edge-colorings
title_sort	on star and biclique edge-colorings
url	http://hdl.handle.net/20.500.12110/paper_09696016_v24_n1-2_p339_Dantas
work_keys_str_mv	AT dantass onstarandbicliqueedgecolorings AT groshausm onstarandbicliqueedgecolorings AT guedesa onstarandbicliqueedgecolorings AT machadorcs onstarandbicliqueedgecolorings AT riesb onstarandbicliqueedgecolorings AT sasakid onstarandbicliqueedgecolorings
_version_	1782023699504824320

On star and biclique edge-colorings

Ejemplares similares