Approximate graph colouring and crystals

Approximate graph colouring and crystals

We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiting a graph fooling a level of the AIP hierarchy into the problem of constructing a highly symmetric crystal tensor. In o...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Ciardo, L, Živný, S
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Society for Industrial and Applied Mathematics 2023

Míreanna comhchosúla

Approximate graph colouring and the hollow shadow
de réir: Zivny, S, et al.
Foilsithe / Cruthaithe: (2023)

Improved hardness for H-colourings of G-colourable graphs
de réir: Wrochna, M, et al.
Foilsithe / Cruthaithe: (2020)

A logarithmic approximation of linearly-ordered colourings
de réir: Håstad, J, et al.
Foilsithe / Cruthaithe: (2024)

The complexity of approximately counting retractions to square-free graphs
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Hierarchies of minion tests for PCSPs through tensors
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

CLAP: A new algorithm for promise CSPs
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

Semidefinite programming and linear equations vs. homomorphism problems
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2024)

Semidefinite programming and linear equations vs. homomorphism problems
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2025)

On approximate graph colouring and max-k-cut algorithms based on the θ-function
de réir: Klerk, Etienne de., et al.
Foilsithe / Cruthaithe: (2013)

Graphs, colourings and the four-colour theorem /
de réir: 374980 Wilson, Robert A.
Foilsithe / Cruthaithe: (2002)

On approximate graph colouring and MAX−k−CUT algorithms based on the ϑ−function
de réir: de Klerk, E, et al.
Foilsithe / Cruthaithe: (2004)

Colourings of random graphs
de réir: Heckel, A
Foilsithe / Cruthaithe: (2016)

Graph colourings and games
de réir: Meeks, KFT
Foilsithe / Cruthaithe: (2012)

Improper colourings of graphs
de réir: Kang, R
Foilsithe / Cruthaithe: (2008)

Balancing connected colourings of graphs
de réir: Illingworth, F, et al.
Foilsithe / Cruthaithe: (2023)

Colouring proximity graphs in the plane
de réir: McDiarmid, C, et al.
Foilsithe / Cruthaithe: (1999)

Graph colouring and other stories
de réir: Guggiari, H
Foilsithe / Cruthaithe: (2019)

Maximising H-colourings of graphs
de réir: Guggiari, H, et al.
Foilsithe / Cruthaithe: (2019)

Cycles in edge-coloured graphs and subgraphs of random graphs
de réir: White, M
Foilsithe / Cruthaithe: (2011)

Approximately counting H-colourings is BIS-Hard
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

Approximately counting H-colourings is #BIS-hard
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2016)

List Colouring Squares of Planar Graphs
de réir: Havet, F, et al.
Foilsithe / Cruthaithe: (2008)

The chromatic profile of locally colourable graphs
de réir: Illingworth, F
Foilsithe / Cruthaithe: (2021)

The chromatic profile of locally colourable graphs
de réir: Illingworth, F
Foilsithe / Cruthaithe: (2022)

Monochromatic Cycles in 2-Coloured Graphs
de réir: Benevides, F, et al.
Foilsithe / Cruthaithe: (2012)

Clique colouring of binomial random graphs
de réir: McDiarmid, C, et al.
Foilsithe / Cruthaithe: (2018)

Linearly ordered colourings of hypergraphs
de réir: Nakajima, T-V, et al.
Foilsithe / Cruthaithe: (2022)

Linearly ordered colourings of hypergraphs
de réir: Nakajima, T-V, et al.
Foilsithe / Cruthaithe: (2022)

Colour (approximate to age?) gradients in spiral galaxies
de réir: deJong, R
Foilsithe / Cruthaithe: (1996)

Algorithms for Approximate Graph Coloring
de réir: Blum, Avrim
Foilsithe / Cruthaithe: (2023)

Acyclic improper colourings of graphs with bounded maximum degree
de réir: Addario-Berry, L, et al.
Foilsithe / Cruthaithe: (2010)

Colouring, centrality and core-periphery structure in graphs
de réir: Rombach, M
Foilsithe / Cruthaithe: (2013)

Coloured graph models: Associating emitters and ships
de réir: Hillebrand, A
Foilsithe / Cruthaithe: (2015)

On rainbow-free colourings of uniform hypergraphs
de réir: Groot Koerkamp, R, et al.
Foilsithe / Cruthaithe: (2021)

A complexity trichotomy for approximately counting list H-colourings
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

A complexity trichotomy for approximately counting list H-colourings
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

An approximation scheme for planar graph TSP
de réir: Grigni, M, et al.
Foilsithe / Cruthaithe: (2015)

Local graph partitions for approximation and testing
de réir: Hassidim, Avinatan, et al.
Foilsithe / Cruthaithe: (2010)

The complexity of approximately counting retractions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2019)

H-colouring Pt-free graphs in subexponential time
de réir: Groenland, C, et al.
Foilsithe / Cruthaithe: (2019)