Coloring of G²∖G, for Euclidesian graph G
Konstanty Junosza-Szaniawski (2005)
Discussiones Mathematicae Graph Theory
Similarity:
Konstanty Junosza-Szaniawski (2005)
Discussiones Mathematicae Graph Theory
Similarity:
Nibedita Mandal, Pratima Panigrahi (2016)
Discussiones Mathematicae Graph Theory
Similarity:
An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring f : V (G) → Z+ ∪ {0} such that |f(u) − f(v)| ≥ 2 for all edges uv of G, and |f(u)−f(v)| ≥ 1 if d(u, v) = 2, where d(u, v) is the distance between vertices u and v in G. The span of an L(2, 1)-coloring is the maximum color (or label) assigned by it. The span of a graph G is the smallest integer λ such that there exists an L(2, 1)-coloring of G with span λ. An L(2, 1)-coloring of a graph with span equal to the span of...
P. Francis, S. Francis Raj (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we obtain bounds for the b- chromatic number of induced subgraphs in terms of the b-chromatic number of the original graph. This turns out to be...
Jennifer Loe, Danielle Middelbrooks, Ashley Morris, Kirsti Wash (2015)
Discussiones Mathematicae Graph Theory
Similarity:
A variation of graph coloring known as a t-tone k-coloring assigns a set of t colors to each vertex of a graph from the set {1, . . . , k}, where the sets of colors assigned to any two vertices distance d apart share fewer than d colors in common. The minimum integer k such that a graph G has a t- tone k-coloring is known as the t-tone chromatic number. We study the 2-tone chromatic number in three different graph products. In particular, given graphs G and H, we bound the 2-tone chromatic...
R. Kalfakakou, G. Nikolakopoulou, E. Savvidou, M. Tsouros (2003)
The Yugoslav Journal of Operations Research
Similarity:
Július Czap, Peter Šugerek, Jaroslav Ivančo (2016)
Discussiones Mathematicae Graph Theory
Similarity:
An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.
Wayne Goddard, Robert Melville (2017)
Open Mathematics
Similarity:
We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set....
Igor Fabrici, Frank Göring (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.
Philippe Meurdesoif, Benoît Rottembourg (2001)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct -uples of colors used to color a given set of -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find...
Dennis Geller, Hudson Kronk (1974)
Fundamenta Mathematicae
Similarity:
Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)
Discussiones Mathematicae Graph Theory
Similarity:
For a nontrivial connected graph G, let c: V(G)→ N 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 χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs...
Wen-Yao Song, Lian-Ying Miao (2017)
Discussiones Mathematicae Graph Theory
Similarity:
A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by 𝜒's(G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4 Δ(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211]. In this paper, we show that...
Dzido, Tomasz, Nowik, Andrzej, Szuca, Piotr (2005)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Tomasz Dzido, Renata Zakrzewska (2006)
Discussiones Mathematicae Graph Theory
Similarity:
The upper domination Ramsey number u(m,n) is the smallest integer p such that every 2-coloring of the edges of Kₚ with color red and blue, Γ(B) ≥ m or Γ(R) ≥ n, where B and R is the subgraph of Kₚ induced by blue and red edges, respectively; Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. In this paper, we show that u(4,4) ≤ 15.
Hoffman, Dean G., Johnson, Peter D.jun. (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Kostochka, Alexandr (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity: