Pages that link to "Item:Q5932643"

The following pages link to On the hardness of approximating the chromatic number (Q5932643):

Displaying 43 items.

• Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions (Q334238) (← links)
• Hardness of computing clique number and chromatic number for Cayley graphs (Q518185) (← links)
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time (Q848637) (← links)
• Complexity of approximation of 3-edge-coloring of graphs (Q975462) (← links)
• Exact complexity of exact-four-colorability (Q1014384) (← links)
• Graph coloring by multiagent fusion search (Q1037448) (← links)
• Priority algorithms for graph optimization problems (Q1041242) (← links)
• Zero knowledge and the chromatic number (Q1276168) (← links)
• On approximating the b-chromatic number (Q1765381) (← links)
• Recognizing DNA graphs is difficult. (Q1868714) (← links)
• Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
• A note on approximating the \(b\)-chromatic number (Q1949121) (← links)
• Notes on tree- and path-chromatic number (Q2058953) (← links)
• Additive non-approximability of chromatic number in proper minor-closed classes (Q2099409) (← links)
• Remarks on proper conflict-free colorings of graphs (Q2099465) (← links)
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph (Q2826231) (← links)
• Matrix Relaxations in Combinatorial Optimization (Q2897308) (← links)
• Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (Q2968149) (← links)
• Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors (Q2968154) (← links)
• Balanced coloring of bipartite graphs (Q3057057) (← links)
• Hypergraph list coloring and Euclidean Ramsey theory (Q3094608) (← links)
• On the complexity of the circular chromatic number (Q3159379) (← links)
• Improved inapproximability results for maximum \(k\)-colorable subgraph (Q3191580) (← links)
• Conditional Hardness for Approximate Coloring (Q3575151) (← links)
• The zero-error side information problem and chromatic numbers (Corresp.) (Q4103444) (← links)
• On the hardness of approximating minimization problems (Q4323730) (← links)
• The Quest for Strong Inapproximability Results with Perfect Completeness (Q5002604) (← links)
• (Q5092401) (← links)
• Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy (Q5096441) (← links)
• (Q5136286) (← links)
• Hardness of Rainbow Coloring Hypergraphs (Q5136325) (← links)
• Colouring graphs when the number of colours is nearly the maximum degree (Q5176002) (← links)
• Linear Index Coding via Semidefinite Programming (Q5410256) (← links)
• Graph-Theoretic Concepts in Computer Science (Q5710819) (← links)
• (Q5743408) (← links)
• (Q5870293) (← links)
• CLAP: A New Algorithm for Promise CSPs (Q5885595) (← links)
• Topology and Adjunction in Promise Constraint Satisfaction (Q5885596) (← links)
• Tensors in computations (Q5887832) (← links)
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank (Q6071819) (← links)
• Two generalizations of proper coloring: hardness and approximability (Q6168932) (← links)
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023 (Q6613402) (← links)
• Coloring tournaments with few colors: algorithms and complexity (Q6654122) (← links)