Displaying similar documents to “The k -metric colorings of a graph”

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

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.

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition N G ( x ) ⊆ N G [ u ] ∪ N G [ v ] , where N G [ x ] = N G ( x ) ∪ x . In particular, this condition is satisfied if x does not center a claw (an induced K 1 , 3 ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G , the X -eccentricity e X ( v ) of a vertex v of G is the distance between v and an X -colored vertex furthest from v . The minimum X -eccentricity among the vertices of G is the X -radius r a d X G of G ...

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers c v for the vertices v ∈ V are given, and the question...

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