Displaying similar documents to “2-Tone Colorings in Graph Products”

Solutions of Some L(2, 1)-Coloring Related Open Problems

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

Coloring subgraphs with restricted amounts of hues

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

The set chromatic number of a graph

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

Bounds for the b-Chromatic Number of Subgraphs and Edge-Deleted Subgraphs

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

A Tight Bound on the Set Chromatic Number

Jean-Sébastien Sereni, Zelealem B. Yilma (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.

Vertex Colorings without Rainbow Subgraphs

Wayne Goddard, Honghai Xu (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal...

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers....

Equitable coloring of Kneser graphs

Robert Fidytek, Hanna Furmańczyk, Paweł Żyliński (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k)...

Equitable Colorings Of Corona Multiproducts Of Graphs

Hanna Furmánczyk, Marek Kubale, Vahan V. Mkrtchyan (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts...

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Vertex coloring the square of outerplanar graphs of low degree

Geir Agnarsson, Magnús M. Halldórsson (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

Coloring with no 2-colored P 4 's.

Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Unique-Maximum Coloring Of Plane Graphs

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.

The cost chromatic number and hypergraph parameters

Gábor Bacsó, Zsolt Tuza (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.

Graph Radiocoloring Concepts

R. Kalfakakou, G. Nikolakopoulou, E. Savvidou, M. Tsouros (2003)

The Yugoslav Journal of Operations Research

Similarity: