Colouring Strong Products
arXiv:2205.04953 · doi:10.1016/j.ejc.2023.103847
Abstract
Recent results show that several important graph classes can be embedded as subgraphs of strong products of simpler graphs classes (paths, small cliques, or graphs of bounded treewidth). This paper develops general techniques to bound the chromatic number (and its popular variants, such as fractional, clustered, or defective chromatic number) of the strong product of general graphs with simpler graphs classes, such as paths, and more generally graphs of bounded treewidth. We also highlight important links between the study of (fractional) clustered colouring of strong products and other topics, such as asymptotic dimension in metric theory and topology, site percolation in probability theory, and the Shannon capacity in information theory.
arXiv comment26 pages, 2 figures: v2. the proofs of Theorem 16 and Lemma 31 have been corrected
References in corpus (21)
- Planar graphs have bounded queue-number
- Hurewicz Theorem for Assouad-Nagata dimension
- The Shannon capacity of a graph and the independence numbers of its powers
- On Tree-Partition-Width
- Improper Colourings inspired by Hadwiger's Conjecture
- A relative of Hadwiger's conjecture
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- Islands in minor-closed classes. I. Bounded treewidth and separators
- Coloring planar graphs with three colors and no large monochromatic components
- Partitioning -minor free graphs into three subgraphs with no large components
- Clustered Graph Coloring and Layered Treewidth
- Clustered Colouring in Minor-Closed Classes
- Defective and Clustered Choosability of Sparse Graphs
- Improved product structure for graphs on surfaces
- Clustered Variants of Hajós' Conjecture
- Islands in graphs on surfaces
- Clustered Coloring of Graphs Excluding a Subgraph and a Minor
- Improper coloring of graphs with no odd clique minor
- Improper coloring of graphs on surfaces
- An analogue of Gromov's waist theorem for coloring the cube
- Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree