Coloring with no 2-colored 's.
Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Displaying similar documents to “Neochromatica”
Coloring with no 2-colored 's.
Further results on the achromatic number
Dennis Geller, Hudson Kronk (1974)
Fundamenta Mathematicae
Similarity:
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...
WORM Colorings of Planar Graphs
J. Czap, S. Jendrol’, J. Valiska (2017)
Discussiones Mathematicae Graph Theory
Similarity:
Given three planar graphs F,H, and G, an (F,H)-WORM coloring of G is a vertex coloring such that no subgraph isomorphic to F is rainbow and no subgraph isomorphic to H is monochromatic. If G has at least one (F,H)-WORM coloring, then W−F,H(G) denotes the minimum number of colors in an (F,H)-WORM coloring of G. We show that (a) W−F,H(G) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is...
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 -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...
On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph.
Axenovich, Maria, Choi, JiHyeok (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
On swell-colored complete graphs.
Ward, C., Szabó, S. (1994)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
Graph color extensions: When Hadwiger's conjecture and embeddings help.
Albertson, Michael O., Hutchinson, Joan P. (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
An improvement to Mathon's cyclotomic Ramsey colorings.
Xu, Xiaodong, Radziszowski, Stanislaw P. (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
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 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....
On Monochromatic Subgraphs of Edge-Colored Complete Graphs
Eric Andrews, Futaba Fujie, Kyle Kolasinski, Chira Lumduanhom, Adam Yusko (2014)
Discussiones Mathematicae Graph Theory
Similarity:
In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the mono- chromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard...