On chromatic number and minimum cut

DOI10.1016/j.jctb.2019.02.007zbMath1428.05092arXiv1407.8035OpenAlexW2963306534MaRDI QIDQ2338633

Meysam Alishahi, Hossein Hajiabolhassan

Publication date: 21 November 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

minimum cutchromatic numberalternating partial 2-coloringtree Kneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (1)

On the Chromatic Number of Matching Kneser Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the chromatic number of general Kneser hypergraphs
• Kneser's conjecture, chromatic number, and homotopy
• Finding good approximate vertex and edge partitions is NP-hard
• Some simplified NP-complete graph problems
• Bounds of the number of disjoint spanning trees
• Chromatic number via Turán number
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Edge-Disjoint Spanning Trees of Finite Graphs
• A new approach to the maximum-flow problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

This page was built for publication: On chromatic number and minimum cut