On star and biclique edge‐colorings | Zendy

Dantas Simone | Zendy; Groshaus Marina | Zendy; Guedes André | Zendy; Machado Raphael C. S. | Zendy; Ries Bernard | Zendy; Sasaki Diana | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On star and biclique edge‐colorings

Author(s) -

Dantas Simone,

Groshaus Marina,

Guedes André,

Machado Raphael C. S.,

Ries Bernard,

Sasaki Diana

Publication year - 2016

Publication title -

international transactions in operational research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.032

H-Index - 52

eISSN - 1475-3995

pISSN - 0969-6016

DOI - 10.1111/itor.12307

Subject(s) - combinatorics , complete bipartite graph , bipartite graph , mathematics , edge coloring , discrete mathematics , chordal graph , graph , graph power , line graph

A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph K p , qof 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 K 1 , 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: K 3 ‐free graphs, chordal bipartite graphs, powers of paths, and powers of cycles.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research