The NP-completeness of automorphic colorings

DOI10.7151/DMGT.1525MaRDI QIDQ2997596zbMATH OpenOpenAlexFDO

Authors G. Mazzuoccolo

Publication date 9 May 2011

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.7151/dmgt.1525

zbMATH Keywords

computational complexitygraph coloringNP-complete problemschromatic parameters

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• NP-completeness of edge-colouring some restricted graphs
• Automorphic chromatic index of generalized Petersen graphs
• NP-completeness of local colorings of graphs
• On the automorphic chromatic index of a graph

Cited in

(2)

• Upper bounds for the automorphic chromatic index of a graph
• Automorphic chromatic index of generalized Petersen graphs

This page was built for publication: The NP-completeness of automorphic colorings

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