Displaying similar documents to “Lower bounds for the colored mixed chromatic number of some classes of graphs”

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

About uniquely colorable mixed hypertrees

Angela Niculitsa, Vitaly Voloshin (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A mixed hypergraph is a triple 𝓗 = (X,𝓒,𝓓) where X is the vertex set and each of 𝓒, 𝓓 is a family of subsets of X, the 𝓒-edges and 𝓓-edges, respectively. A k-coloring of 𝓗 is a mapping c: X → [k] such that each 𝓒-edge has two vertices with the same color and each 𝓓-edge has two vertices with distinct colors. 𝓗 = (X,𝓒,𝓓) is called a mixed hypertree if there exists a tree T = (X,𝓔) such that every 𝓓-edge and every 𝓒-edge induces a subtree of T. A mixed hypergraph 𝓗 is...

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers....

On multiset colorings of graphs

Futaba Okamoto, Ebrahim Salehi, Ping Zhang (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset...

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

Coloring with no 2-colored P 4 's.

Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

List coloring of complete multipartite graphs

Tomáš Vetrík (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.