A characterization of easily testable induced digraphs and k-colored graphs

DOI10.1016/J.EJC.2022.103516zbMATH Open1487.05105arXiv2201.11447OpenAlexW4214727906MaRDI QIDQ2136197FDOQ2136197

Lior Gishboliner

Publication date: 10 May 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We complete the characterization of the digraphs $D$ for which the induced $D$-removal lemma has polynomial bounds, answering a question of Alon and Shapira. We also study the analogous problem for $k$-colored complete graphs. In particular, we prove a removal lemma with polynomial bounds for Gallai colorings.

Full work available at URL: https://arxiv.org/abs/2201.11447

zbMATH Keywords

regularityproperty testing\(k\)-colored complete graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing subgraphs in directed graphs
• Efficient testing of large graphs
• Transitiv orientierbare Graphen
• A new proof of the graph removal lemma
• Edge colorings of complete graphs without tricolored triangles
• Testing subgraphs in large graphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Introduction to Property Testing
• Easily Testable Graph Properties
• Efficient removal without efficient regularity
• The removal lemma for tournaments
• Removal lemmas with polynomial bounds

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: A characterization of easily testable induced digraphs and \(k\)-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136197)