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

DOI10.1016/J.EJC.2022.103516MaRDI QIDQ2136197zbMATH OpenOpenAlexFDO

Authors Lior Gishboliner

Publication date 10 May 2022

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• A new proof of the graph removal lemma
• The removal lemma for tournaments
• The induced removal lemma in sparse graphs
• Testing \(k\)-colorability

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A new proof of the graph removal lemma
• Easily testable graph properties
• Edge colorings of complete graphs without tricolored triangles
• Efficient removal without efficient regularity
• Efficient testing of large graphs
• Introduction to Property Testing
• Testing subgraphs in directed graphs
• Testing subgraphs in large graphs
• The removal lemma for tournaments
• Transitiv orientierbare Graphen

Cited in

(1)

• scientific article; zbMATH DE number 6469238 (Why is no real title available?)

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)