Displaying similar documents to “Clique parts independent of remainders”

The B-Domatic Number of a Graph

Odile Favaron (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Besides the classical chromatic and achromatic numbers of a graph related to minimum or minimal vertex partitions into independent sets, the b-chromatic number was introduced in 1998 thanks to an alternative definition of the minimality of such partitions. When independent sets are replaced by dominating sets, the parameters corresponding to the chromatic and achromatic numbers are the domatic and adomatic numbers d(G) and ad(G). We introduce the b-domatic number bd(G) as the counterpart...

A ramsey-type theorem for multiple disjoint copies of induced subgraphs

Tomoki Nakamigawa (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of...

Combinatorial interpretations for identities using chromatic partitions

Mateus Alegri, Wagner Ferreira Santos, Samuel Brito Silva (2021)

Czechoslovak Mathematical Journal

Similarity:

We provide combinatorial interpretations for three new classes of partitions, the so-called chromatic partitions. Using only combinatorial arguments, we show that these partition identities resemble well-know ordinary partition identities.

Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt, Vincent Jost, Maurice Queyranne (2007)

RAIRO - Operations Research

Similarity:

Given a graph and a “cost function” f : 2 V → ℝ (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where is an interval graph and belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the coloring problem...