On the number of boundary classes in the 3-colouring problem
From MaRDI portal
Publication:3225901
DOI10.1515/DMA.2009.043zbMath1237.05083MaRDI QIDQ3225901
Publication date: 23 March 2012
Published in: Discrete Mathematics and Applications (Search for Journal in Brave)
Related Items
Two complexity results for the vertex coloring problem, Boundary properties of graphs for algorithmic graph problems, Boundary graph classes for some maximum induced subgraph problems
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Boundary classes of graphs for the dominating set problem
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- Polynomial algorithm for finding the largest independent sets in graphs without forks