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...

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...

Equitable coloring of Kneser graphs

Robert Fidytek, Hanna Furmańczyk, Paweł Żyliński (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k)...