Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs

DOI10.1007/s00453-015-0106-7zbMath1359.05043OpenAlexW2226560684MaRDI QIDQ521809

Celina M. Herrera de Figueiredo, Raphael C. S. Machado, Hélio B. Macêdo Filho

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0106-7

zbMATH Keywords

decompositionhypergraphsbiclique colouringclique colouringunichord-free graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Complexity-separating graph classes for vertex, edge and total colouring ⋮ Biclique graphs of split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of clique coloring and related problems
• Generating bicliques of a graph in lexicographic order
• Total chromatic number of unichord-free graphs
• The strong perfect graph theorem
• Total colouring regular bipartite graphs is NP-hard
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• A fast algorithm for building lattices
• Chromatic index of graphs with no cycle with a unique chord
• On independent sets and bicliques in graphs
• Total chromatic number of {square,unichord}-free graphs
• Clique-Colouring and Biclique-Colouring Unichord-Free Graphs
• Complexity of clique-coloring odd-hole-free graphs
• The NP-completeness column: an ongoing guide
• The NP-Completeness of Edge-Coloring
• A fast incremental algorithm for building lattices
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Biclique graphs and biclique matrices
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Decomposing and Clique‐Coloring (Diamond, Odd‐Hole)‐Free Graphs
• Node-and edge-deletion NP-complete problems
• The Star and Biclique Coloring and Choosability Problems
• Depth-First Search and Linear Graph Algorithms
• On the generation of bicliques of a graph
• Bicliques in graphs. I: Bounds on their number

This page was built for publication: Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs