Chromatic characterization of biclique covers

DOI10.1016/j.disc.2006.01.010zbMath1087.05043OpenAlexW2147972841MaRDI QIDQ2368922

Jean Fonlupt, Denis Cornaz

Publication date: 28 April 2006

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2006.01.010

zbMATH Keywords

bipartitechromatic numberclique number

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

On computing the Galois lattice of bipartite distance hereditary graphs ⋮ An overview of graph covering and partitioning ⋮ Unnamed Item ⋮ A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints ⋮ Minimal arc-sets spanning dicycles ⋮ Edge cover by connected bipartite subgraphs ⋮ On co-bicliques ⋮ Covering Graphs with Few Complete Bipartite Subgraphs ⋮ Covering graphs with few complete bipartite subgraphs ⋮ A linear programming formulation for the maximum complete multipartite subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consensus algorithms for the generation of all maximal bicliques
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Bipartite dimensions and bipartite degrees of graphs
• On the coverings of graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• The maximum edge biclique problem is NP-complete
• On edge perfectness and classes of bipartite graphs
• On Approximate Solutions for Combinatorial Optimization Problems
• The biparticity of a graph

This page was built for publication: Chromatic characterization of biclique covers