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

DOI10.1007/S00453-015-0106-7MaRDI QIDQ521809zbMATHOpenAlexFDO

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

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

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

Recommendations

• Clique-colouring and biclique-colouring unichord-free graphs
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Complexity separating classes for edge-colouring and total-colouring
• Total chromatic number of unichord-free graphs
• Total chromatic number of \{square,unichord\}-free graphs

Cites work

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

Cited in

(7)

• Complexity-separating graph classes for vertex, edge and total colouring
• Biclique-colouring verification complexity and biclique-colouring power graphs
• scientific article; zbMATH DE number 6469209 (Why is no real title available?)
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Clique-colouring and biclique-colouring unichord-free graphs
• Total chromatic number of unichord-free graphs
• Biclique graphs of split graphs

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

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