On star and biclique edge-colorings

DOI10.1111/itor.12307zbMath1358.05100OpenAlexW2466096890MaRDI QIDQ2968507

André L. P. Guedes, Bernard Ries, Simone Dantas, Marina Groshaus, Raphael C. S. Machado, Diana Sasaki

Publication date: 16 March 2017

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/324393/files/biclique_rero.pdf

zbMATH Keywords

NP-hardnessstar edge-coloringbiclique edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the complexity of coloring ‐graphs ⋮ Biclique graphs of split graphs

Cites Work

• The 1,2-conjecture for powers of cycles
• Biclique-colouring verification complexity and biclique-colouring power graphs
• Complexity of clique coloring and related problems
• Colouring vertices of triangle-free graphs without forests
• A result on the total colouring of powers of cycles
• On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs
• Biclique completion problems for multicast network design
• Clique-Colouring and Biclique-Colouring Unichord-Free Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• A branch‐and‐price approach to k‐clustering minimum biclique completion problem
• The Star and Biclique Coloring and Choosability Problems