On the Complexity of Ordered Colorings

DOI10.1137/060676222MaRDI QIDQ3629479zbMATH OpenOpenAlexFDO

Authors Arvind Kumar Gupta, Jan van den Heuvel, Ján Maňuch, Ladislav Stacho, Xiaohong Zhao

Publication date 27 May 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/7f100266cb6ab056403fe272a1cfb25dd43b4f7d

zbMATH Keywords

complexitydirected graph homomorphismgraph coloringNP-completenessordered coloringpolynomial algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Ordered colourings
• Ordered coloring of grids and related graphs
• Colourings, homomorphisms, and partitions of transitive digraphs
• scientific article; zbMATH DE number 1953088
• scientific article; zbMATH DE number 817188

Cited in

(10)

• Sequential coloring versus Welsh-Powell bound
• Fibres and ordered set coloring
• On the Complexity of Some Ordering Problems
• On first-order definable colorings
• scientific article; zbMATH DE number 4053647 (Why is no real title available?)
• Coloring Ordered Sets to Avoid Monochromatic Maximal Chains
• Ordered coloring of grids and related graphs
• On the complexity of the flow coloring problem
• Coloring linear orders with Rado's partial order
• On the restricted homomorphism problem

This page was built for publication: On the Complexity of Ordered Colorings

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