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

DOI10.1515/DMA.2009.043MaRDI QIDQ3225901zbMATH OpenFDO

Authors D. 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)

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

Cites work

• Boundary classes of graphs for the dominating set problem
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• The ellipsoid method and its consequences in combinatorial optimization

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)