The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size

DOI10.1016/j.disc.2023.113342OpenAlexW4318953856MaRDI QIDQ2685343

Sophie Spirkl, Yanjia Li

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

zbMATH Keywords

hypergraphmatching numberlinear hypergraphcoloring algorithminduced subhypergraph

Mathematics Subject Classification ID

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