On the number of boundary classes in the 3-colouring problem

DOI10.1515/DMA.2009.043zbMath1237.05083MaRDI QIDQ3225901

Dmitriy S. Malyshev

Publication date: 23 March 2012

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

zbMATH Keywords

complexity of extremal problems on graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Boundary graph classes for some maximum induced subgraph problems ⋮ Two complexity results for the vertex coloring problem ⋮ Boundary properties of graphs for algorithmic graph 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

This page was built for publication: On the number of boundary classes in the 3-colouring problem