Chromatic characterization of biclique covers

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

Denis Cornaz, Jean Fonlupt

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

bipartite; chromatic number; clique number

Mathematics Subject Classification ID

90C10: Integer programming

90C05: Linear programming

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Covering Graphs with Few Complete Bipartite Subgraphs, Edge cover by connected bipartite subgraphs, Covering graphs with few complete bipartite subgraphs, A linear programming formulation for the maximum complete multipartite subgraph problem, On co-bicliques

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