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.