Displaying similar documents to “The NP-completeness of automorphic colorings”

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

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

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

M 2 -Edge Colorings Of Cacti And Graph Joins

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.

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.

2-Tone Colorings in Graph Products

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

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 Note on Neighbor Expanded Sum Distinguishing Index

Evelyne Flandrin, Hao Li, Antoni Marczyk, Jean-François Saclé, Mariusz Woźniak (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

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:

The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

Poppy Immel, Paul S. Wenger (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the...

Worm Colorings

Wayne Goddard, Kirsti Wash, Honghai Xu (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes....

Rainbow H -factors.

Yuster, Raphael (2006)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Semi-definite positive programming relaxations for graph K 𝐧 -coloring in frequency assignment

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 n -uples of colors used to color a given set of n -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...

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.