Displaying similar documents to “ T -preserving homomorphisms of oriented graphs”

Set colorings in perfect graphs

Ralucca Gera, Futaba Okamoto, Craig Rasmussen, Ping Zhang (2011)

Mathematica Bohemica

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 ∈ V ( 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 ) . We show that the decision variant of determining χ s ( G ) is NP-complete in the general case, and show that...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph G is said to be an i n t e g r a l s u m g r a p h if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G , u v is an edge of G if and only if f ( u ) + f ( v ) = f ( w ) for some vertex w in G . We prove that every integral sum graph with a saturated vertex, except the complete graph K 3 , has edge-chromatic number equal to its maximum degree. (A vertex of a graph G is said to be if it is adjacent to every...

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