In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut.
Let $H$ be a fixed …
Let $H$ be a fixed undirected graph. A vertex coloring of an undirected input graph $G$ is said to be an $H$-Free Coloring if none of the color classes contain $H$ as an induced subgraph. The $H$-Free Chromatic Number of $G$ is the minimum number of …
In this paper we prove that two local conditions involving the degrees and co-degrees in a graph can be used to determine whether a given vertex partition is Frieze–Kannan regular. With a more refined version of these two local conditions we provide …
The Frieze-Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The …