The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
From MaRDI portal
Publication:2685343
DOI10.1016/j.disc.2023.113342OpenAlexW4318953856MaRDI QIDQ2685343
Publication date: 21 February 2023
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.10393
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Colouring vertices of triangle-free graphs without forests
- On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
- A constructive proof of Vizing's theorem
- Some simplified NP-complete graph problems
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Properly 2-Colouring Linear Hypergraphs
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Reducibility among Combinatorial Problems
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
This page was built for publication: The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size