Displaying similar documents to “Set colorings in perfect graphs”

Set vertex colorings and joins of graphs

Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)

Czechoslovak Mathematical Journal

Similarity:

For a nontrivial connected graph G , let c V ( G ) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G , the neighborhood color set NC ( v ) is the set of colors of the neighbors of v . The coloring c is called a set coloring if NC ( u ) ≠ NC ( v ) for every pair u , v of adjacent vertices of G . The minimum number of colors required of such a coloring is called the set chromatic number χ s ( G ) . A study is made of the set chromatic number of the join G + H of two graphs G and H . Sharp lower...

T -preserving homomorphisms of oriented graphs

Jaroslav Nešetřil, Eric Sopena, Laurence Vignal (1997)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A homomorphism of an oriented graph G = ( V , A ) to an oriented graph G ' = ( V ' , A ' ) is a mapping ϕ from V to V ' such that ϕ ( u ) ϕ ( v ) is an arc in G ' whenever u v is an arc in G . A homomorphism of G to G ' is said to be T -preserving for some oriented graph T if for every connected subgraph H of G isomorphic to a subgraph of T , H is isomorphic to its homomorphic image in G ' . The T -preserving oriented chromatic number χ → T ( G ) of an oriented graph G is the minimum number of vertices in an oriented graph G ' such that there exists a T -preserving...

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph K k + 1 by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Upper bounds on the b-chromatic number and results for restricted graph classes

Mais Alkhateeb, Anja Kohl (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number χ b ( G ) is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying χ ( G ) ≤ k ≤ χ b ( G ) . In this paper, we establish four general upper bounds on χ b ( G ) . We present results on the b-chromatic...