Displaying similar documents to “Frequency planning and ramifications of coloring”

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

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Krzysztof Giaro, Marek Kubale (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.

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:

Neochromatica

Panagiotis Cheilaris, Ernst Specker, Stathis Zachos (2010)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We create and discuss several modifications to traditional graph coloring. In particular, we classify various notions of coloring in a proper hierarchy. We concentrate on grid graphs whose colorings can be represented by natural number entries in arrays with various restrictions.

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

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

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.

Three edge-coloring conjectures

Richard H. Schelp (2002)

Discussiones Mathematicae Graph Theory

Similarity:

The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.