Robust Factorizations and Colorings of Tensor Graphs
DOI10.1137/23m1552474arXiv2207.08913OpenAlexW4392237528MaRDI QIDQ6195952
Sami Davies, Joshua Brakensiek
Publication date: 14 March 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2207.08913
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Factoring a graph in polynomial time
- Local algorithms for the prime factorization of strong product graphs
- Finding the prime factors of strong direct product graphs in polynomial time
- The core of a graph
- A note on Winkler's algorithm for factoring a connected graph
- Recognizing Cartesian products in linear time
- Weak reconstruction of strong product graphs
- A better performance guarantee for approximate graph coloring
- Approximate graph products
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
- Factoring cardinal product graphs in polynomial time
- The ubiquitous Kronecker product
- Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
- New approximation guarantee for chromatic number
- New Tools for Graph Coloring
- Algorithmic Aspects of Machine Learning
- Coloring 3-Colorable Graphs with Less than n 1/5 Colors
- Conditional Hardness for Approximate Coloring
- Forbidden Intersections
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- Product graph representations
- Applications of product colouring
- On the Computational Complexity of Combinatorial Problems
- New approximation algorithms for graph coloring
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On Factorable Extensions and Subgraphs of Prime Graphs
- Max Cut and the Smallest Eigenvalue
- Algebraic Approach to Promise Constraint Satisfaction
- Beyond the Worst-Case Analysis of Algorithms
- Improved hardness for H-colourings of G-colourable graphs
- New hardness results for graph and hypergraph colorings
- On recognizing Cartesian graph bundles
- Wiener index of trees: Theory and applications
This page was built for publication: Robust Factorizations and Colorings of Tensor Graphs
