The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Defective choosability of graphs in surfaces”

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

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

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.

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang (2002)

Mathematica Bohemica

Similarity:

A radio antipodal coloring of a connected graph G with diameter d is an assignment of positive integers to the vertices of G , with x ∈ V ( G ) assigned c ( x ) , such that d ( u , v ) + | c ( u ) - c ( v ) | ≥ d for every two distinct vertices u , v of G , where d ( u , v ) is the distance between u and v in G . The radio antipodal coloring number a c ( c ) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G . The radio antipodal chromatic number a c ( G ) of G is min { a c ( c ) } over all radio antipodal colorings c of G . Radio antipodal chromatic numbers...

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

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

3-consecutive c-colorings of graphs

Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, M.S. Subramanya, Charles Dominic (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ( χ ̅ ) 3 C C ( G ) of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ( χ ̅ ) 3 C C ( G ) ≥ k for k = 3 and k = 4.