A study of the boundary graph classes for colorability problems

DOI10.1134/S1990478913020117zbMATH Open1324.05063MaRDI QIDQ5263795FDOQ5263795

Authors: D. S. Malyshev 

Publication date: 17 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Recommendations

• Continuous sets of the boundary classes of graphs for coloring problems
• Bounded vertex colorings of graphs
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• On Hypergraph and Graph Isomorphism with Bounded Color Classes
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• The classification of graphs on edge covering coloring
• Boundary classes of graphs for the dominating set problem
• Complexity classification of the edge coloring problem for a family of graph classes
• Colouring graphs with bounded generalized colouring number
• The complexity of some graph colouring problems

zbMATH Keywords

computational complexityboundary class of graphscolorability problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Cited In (9)

• Vertex coloring of graphs with few obstructions
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Continuous sets of the boundary classes of graphs for coloring problems
• On the number of boundary classes in the 3-colouring problem
• On integer programming with bounded determinants
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Critical hereditary graph classes: a survey
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number

This page was built for publication: A study of the boundary graph classes for colorability problems

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