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

DOI10.1515/DMA.2009.043zbMATH Open1237.05083MaRDI QIDQ3225901FDOQ3225901

Authors: D. S. Malyshev 

Publication date: 23 March 2012

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

Recommendations

• Continuous sets of the boundary classes of graphs for coloring problems
• A study of the boundary graph classes for colorability problems
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Boundary classes of graphs for the dominating set problem
• Boundary classes of graphs for some recognition problems

zbMATH Keywords

complexity of extremal problems on graphs

Mathematics Subject Classification ID

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

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
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• The 3-Colorability Problem on Graphs with Maximum Degree Four

Cited In (5)

• Boundary properties of graphs for algorithmic graph problems
• Continuous sets of the boundary classes of graphs for coloring problems
• Boundary graph classes for some maximum induced subgraph problems
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Two complexity results for the vertex coloring problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225901)