On star and biclique edge-colorings

DOI10.1111/ITOR.12307zbMATH Open1358.05100OpenAlexW2466096890MaRDI QIDQ2968507FDOQ2968507

Authors: Simone Dantas, Marina Groshaus, André L. P. Guedes, Bernard Ries, R. 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

Recommendations

• The Star and Biclique Coloring and Choosability Problems
• Biclique-colouring verification complexity and biclique-colouring power graphs
• On star edge colorings of bipartite and subcubic graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• On restricted edge-colorings of bicliques

zbMATH Keywords

NP-hardnessstar edge-coloringbiclique edge-coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• On the complexity of coloring ‐graphs
• Chromatic characterization of biclique covers
• Edge-colorings avoiding fixed rainbow stars
• On the complexity of bicoloring clique hypergraphs of graphs
• Title not available (Why is that?)
• On restricted edge-colorings of bicliques
• The Star and Biclique Coloring and Choosability Problems
• Exact algorithms for biclique coloring
• A polynomial algorithm for finding \((g,f)\)-colorings orthogonal to stars in bipartite graphs
• Intersection graph of maximal stars
• Title not available (Why is that?)
• Biclique graphs of split graphs

This page was built for publication: On star and biclique edge-colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968507)