Cover Image

Color Refinement for Relational Structures

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Scheidt, Benjamin, Schweikardt, Nicole
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
by: Antoniadis, Antonios, et al.
Published: (2025)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

A Customized SAT-based Solver for Graph Coloring
by: Brand, Timo, et al.
Published: (2025)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
by: Antony, Dhanyamol, et al.
Published: (2023)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2022)

Solving the List Coloring Problem through a Branch-and-Price algorithm
by: Lucci, Mauro, et al.
Published: (2023)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Relative-error monotonicity testing
by: Chen, Xi, et al.
Published: (2024)

Relative-error unateness testing
by: Chen, Xi, et al.
Published: (2025)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

On the Structural Parameterizations of 2-Club with Triangle Constraints
by: Jacob, Ashwin, et al.
Published: (2025)