A study of the boundary graph classes for colorability problems

DOI10.1134/S1990478913020117MaRDI QIDQ5263795zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 17 July 2015

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

zbMATH Keywords

computational complexityboundary class of graphscolorability problem

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)