Hitting all maximal independent sets of a bipartite graph

DOI10.1007/s00453-013-9847-3zbMath1328.05139arXiv1208.5589OpenAlexW3105919819MaRDI QIDQ2354017

Jean Cardinal, Gwenaël Joret

Publication date: 10 July 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.5589

zbMATH Keywords

maximal independent setclique transversalfiber in posets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Transversal (matching) theory (05D15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Covering partial cubes with zones

Cites Work

• Complexity of clique coloring and related problems
• Clique-transversal sets of line graphs and complements of line graphs
• Algorithms for finding clique-transversals of graphs
• Chains, antichains, and fibres
• Covering all cliques of a graph
• Two-colouring all two-element maximal antichains
• Fibres and ordered set coloring
• Covering the cliques of a graph with vertices
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• On the clique-transversal number of chordal graphs
• On clique-transversals and clique-independent sets
• Algorithmic aspects of clique-transversal and clique-independent sets
• Complexity of automaton identification from given data
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Unnamed Item

This page was built for publication: Hitting all maximal independent sets of a bipartite graph