The distinguishing chromatic number.
Collins, Karen L., Trenk, Ann N. (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Collins, Karen L., Trenk, Ann N. (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Hajo Broersma, Xueliang Li (1997)
Discussiones Mathematicae Graph Theory
Similarity:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard. ...
Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for every set S of k vertices of V (G) is called the k-rainbow index of G, denoted...
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...
Dumitrescu, Adrian, Guha, Sumanta (2004)
Journal of Graph Algorithms and Applications
Similarity:
Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ N, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree connecting S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of...
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....
Petr Gregor, Riste Škrekovski (2012)
Discussiones Mathematicae Graph Theory
Similarity:
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
Picollelli, Michael E. (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
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.
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...
Xu, Xiaodong, Radziszowski, Stanislaw P. (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity: