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
Autor principal: Groshaus, Marina E.
Publicado: 2017
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09696016_v24_n1-2_p339_Dantas
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 paper:paper_09696016_v24_n1-2_p339_Dantas
record_format dspace
spelling paper:paper_09696016_v24_n1-2_p339_Dantas2023-06-08T15:59:03Z On star and biclique edge-colorings Groshaus, Marina E. 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. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09696016_v24_n1-2_p339_Dantas 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
Groshaus, Marina E.
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.
author Groshaus, Marina E.
author_facet Groshaus, Marina E.
author_sort Groshaus, Marina E.
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
publishDate 2017
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09696016_v24_n1-2_p339_Dantas
http://hdl.handle.net/20.500.12110/paper_09696016_v24_n1-2_p339_Dantas
work_keys_str_mv AT groshausmarinae onstarandbicliqueedgecolorings
_version_ 1768546548932673536

Ejemplares similares