Some examples related to colorings

Michael van Hartskamp; Jan van Mill

Displaying similar documents to “Some examples related to colorings”

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.

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

Radio k-colorings of paths

Gary Chartrand, Ladislav Nebeský, Ping Zhang (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings...

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_{v}$ for the vertices v ∈ V are given, and the question...

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

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

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

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

Indestructible colourings and rainbow Ramsey theorems

Lajos Soukup (2009)

Fundamenta Mathematicae

Similarity:

We show that if a colouring c establishes ω₂ ↛ [(ω₁:ω)]² then c establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of c is Cohen-indestructible. This result yields a negative answer to a question of Erdős and Hajnal: it is consistent that GCH holds and there is a colouring c:[ω₂]² → 2 establishing ω₂ ↛ [(ω₁:ω)]₂ such that some colouring g:[ω₁]² → 2 does not embed into c. It is also consistent that $2^{ω ₁}$ is arbitrarily large,...

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.

Coloring grids

Ramiro de la Vega (2015)

Fundamenta Mathematicae

Similarity:

A structure $= {(A; E_{i})}_{i \in n}$ where each $E_{i}$ is an equivalence relation on A is called an n-grid if any two equivalence classes coming from distinct $E_{i}$ ’s intersect in a finite set. A function χ: A → n is an acceptable coloring if for all i ∈ n, the $χ^{- 1} (i)$ intersects each $E_{i}$ -equivalence class in a finite set. If B is a set, then the n-cube Bⁿ may be seen as an n-grid, where the equivalence classes of $E_{i}$ are the lines parallel to the ith coordinate axis. We use elementary submodels of the universe to characterize...

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

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph $ℋ_{d ̲, d ̅} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ < | e | < d ̅ \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices $w ₁, . . ., w_{σ} \notin V$ such that $ℋ \cup w ₁, . . ., w_{σ}$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition...

Maximum Edge-Colorings Of Graphs

Stanislav Jendrol’, Michaela Vrbjarová (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $χ_{r}^{'} (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $χ_{r}^{'} (G) \leq 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i...

The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph $⁺_{d} (S) = (V,)$ , where V = S and $= v ₁, . . ., v_{d} : (i \neq j \Rightarrow v_{i} \neq v_{j}) \land \sum_{i = 1}^{d} v_{i} \in S$ . For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w ₁, . . ., w_{σ} \notin V$ such that $\cup w ₁, . . ., w_{σ}$ is a sum hypergraph. In this paper, we prove $σ (_{n ₁, . . ., n_{d}}^{d}) = 1 + \sum_{i = 1}^{d} (n_{i} - 1) + m i n 0, ⌈ 1 / 2 (\sum_{i = 1}^{d - 1} (n_{i} - 1) - n_{d}) ⌉$ , where $_{n ₁, . . ., n_{d}}^{d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang (2008)

Mathematica Bohemica

Similarity:

Let $G$ be a nontrivial connected graph on which is defined a coloring $c E (G) \to {1, 2, ..., k}$ , $k \in ℕ$ , of the edges of $G$ , where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ contains a rainbow $u - v$ path for every two vertices $u$ and $v$ of $G$ . The minimum $k$ for which there exists such a $k$ -edge coloring is the rainbow connection number $r c (G)$ of $G$ . If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u - v$ geodesic,...