Graph colorings with local constraints - a survey

Zsolt Tuza

Displaying similar documents to “Graph colorings with local constraints - a survey”

3-consecutive c-colorings of graphs

Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, M.S. Subramanya, Charles Dominic (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ${(χ ̅)}_{3 C C} (G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ${(χ ̅)}_{3 C C} (G) \geq k$ for k = 3 and k = 4.

Fall coloring of graphs I

Rangaswami Balakrishnan, T. Kavaskar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A fall coloring of a graph G is a proper coloring of the vertex set of G such that every vertex of G is a color dominating vertex in G (that is, it has at least one neighbor in each of the other color classes). The fall coloring number $χ_{f} (G)$ of G is the minimum size of a fall color partition of G (when it exists). Trivially, for any graph G, $χ (G) \leq χ_{f} (G)$ . In this paper, we show the existence of an infinite family of graphs G with prescribed values for χ(G) and $χ_{f} (G)$ . We also obtain the smallest non-fall...

Localization of jumps of the point-distinguishing chromatic index of $K_{n, n}$

Mirko Horňák, Roman Soták (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of $K_{n, n}$ is found.

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers $s_{i}$ and $t_{i}$ satisfying $1 \leq s_{i} \leq t_{i} \leq | E_{i} |$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_{i}$ satisfies $s_{i} \leq | φ (E_{i}) | \leq t_{i}$ . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each $E_{i}$ induces a connected subgraph in G....

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$ -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$ , the $X$ -eccentricity $e_{X} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$ -colored vertex furthest from $v$ . The minimum $X$ -eccentricity among the vertices of $G$ is the $X$ -radius ${r a d}_{X} G$ of $G$ ...

Two variants of the size Ramsey number

Andrzej Kurek, Andrzej Ruciński (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m (G) = m a x_{F \subseteq G} | E (F) | / | V (F) |$ and define the Ramsey density $m_{i n f} (H, r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{i n f} (H, r) = (R - 1) / 2$ , where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited...

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k + 1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer $k$ , induced subgraphs in which each component has order at most $k$ . Such a subgraph is said to be $k$ -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$ -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

Upper bounds on the b-chromatic number and results for restricted graph classes

Mais Alkhateeb, Anja Kohl (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number $χ_{b} (G)$ is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying $χ (G) \leq k \leq χ_{b} (G)$ . In this paper, we establish four general upper bounds on $χ_{b} (G)$ . We present results on the b-chromatic...

The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami, Lutz Volkmann (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set 1,2, ...,k such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃u ∈ N(v)f(u) = 1,2, ...,k is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set $f ₁, f ₂, . . ., f_{d}$ of k-rainbow dominating functions on G with the property that $\sum_{i = 1}^{d} | f_{i} (v) | \leq k$ for each v ∈ V(G), is called a k-rainbow dominating...

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph $^{\to} G$ is the minimum order of an oriented graph $^{\to} H$ such that $^{\to} G$ admits a homomorphism to $^{\to} H$ . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^{\to} U$ such that every orientation $^{\to} G$ of G admits a homomorphism to $^{\to} U$ . We give...

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...