Coloring triangles and rectangles

Jindřich Zapletal

Displaying similar documents to “Coloring triangles and rectangles”

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

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d ̲, [d ̅]} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ \leq | e | \leq [d ̅] \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y ₁, . . ., y_{σ} \notin V$ such that $\cup y ₁, . . ., y_{σ}$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

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

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.

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.

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

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

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

Algebraic Superconnections, $S U (2 ∣ 1)$ and Electroweak Interactions

R. Coquereaux (1992)

Recherche Coopérative sur Programme n°25

Similarity:

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.

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

Cycles on algebraic models of smooth manifolds

Wojciech Kucharz (2009)

Journal of the European Mathematical Society

Similarity:

Every compact smooth manifold $M$ is diffeomorphic to a nonsingular real algebraic set, called an algebraic model of $M$ . We study modulo 2 homology classes represented by algebraic subsets of $X$ , as $X$ runs through the class of all algebraic models of $M$ . Our main result concerns the case where $M$ is a spin manifold.

Generalized list colourings of graphs

Mieczysław Borowiecki, Ewa Drgas-Burchardt, Peter Mihók (1995)

Discussiones Mathematicae Graph Theory

Similarity:

We prove: (1) that $c h_{P} (G) - χ_{P} (G)$ can be arbitrarily large, where $c h_{P} (G)$ and $χ_{P} (G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Donghan Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V (G), E (G))$ be a simple graph and $E_{G} (v)$ denote the set of edges incident with a vertex $v$ . A neighbor sum distinguishing (NSD) total coloring $φ$ of $G$ is a proper total coloring of $G$ such that $\sum_{z \in E_{G} (u) \cup {u}} φ (z) \neq \sum_{z \in E_{G} (v) \cup {v}} φ (z)$ for each edge $u v \in E (G)$ . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $Δ$ admits an NSD total $(Δ + 3)$ -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $Δ \geq 11$ but without $5$ -cycles by applying the Combinatorial Nullstellensatz.

Some examples related to colorings

Michael van Hartskamp, Jan van Mill (2000)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We complement the literature by proving that for a fixed-point free map $f : X \to X$ the statements (1) $f$ admits a finite functionally closed cover $𝒜$ with $f [A] \cap A = \emptyset$ for all $A \in 𝒜$ (i.e., a coloring) and (2) $β f$ is fixed-point free are equivalent. When functionally closed is weakened to closed, we show that normality is sufficient to prove equivalence, and give an example to show it cannot be omitted. We also show that a theorem due to van Mill is sharp: for every $n \geq 2$ we construct a strongly zero-dimensional Tychonov...