Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás; Zsolt Tuza; Vitaly Voloshin

Displaying similar documents to “Color-bounded hypergraphs, V: host graphs and subdivisions”

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

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

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.

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

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.

Bounds for the number of meeting edges in graph partitioning

Qinghou Zeng, Jianfeng Hou (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that $G$ admits a bipartition such that each vertex class meets edges of total weight at least $(w_{1} - Δ_{1}) / 2 + 2 w_{2} / 3$ , where $w_{i}$ is the total weight of edges of size $i$ and $Δ_{1}$ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph $G$ (i.e., multi-hypergraph), we show that there exists a bipartition of $G$ such that each vertex class meets edges of total weight at least $(w_{0} - 1) / 6 + (w_{1} - Δ_{1}) / 3 + 2 w_{2} / 3$ , where...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

Edge-sum distinguishing labeling

Jan Bok, Nikola Jedličková (2021)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We study edge-sum distinguishing labeling, a type of labeling recently introduced by Z. Tuza (2017) in context of labeling games. An ESD labeling of an $n$ -vertex graph $G$ is an injective mapping of integers $1$ to $l$ to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If $l$ equals to $n$ , we speak about a canonical ESD labeling. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not...

On $g_{c}$ -colorings of nearly bipartite graphs

Yuzhuo Zhang, Xia Zhang (2018)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a simple graph, let $d (v)$ denote the degree of a vertex $v$ and let $g$ be a nonnegative integer function on $V (G)$ with $0 \leq g (v) \leq d (v)$ for each vertex $v \in V (G)$ . A $g_{c}$ -coloring of $G$ is an edge coloring such that for each vertex $v \in V (G)$ and each color $c$ , there are at least $g (v)$ edges colored $c$ incident with $v$ . The $g_{c}$ -chromatic index of $G$ , denoted by $χ_{g_{c}}^{'} (G)$ , is the maximum number of colors such that a $g_{c}$ -coloring of $G$ exists. Any simple graph $G$ has the $g_{c}$ -chromatic index equal to $δ_{g} (G)$ or $δ_{g} (G) - 1$ , where $δ_{g} (G) = {min}_{v \in V (G)} ⌊ d (v) / g (v) ⌋$ . A graph $G$ is nearly bipartite,...

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

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{- α}$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n \to \infty$ , the terminal density of fireproof...

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Similarity:

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$ , a hereditary graph property $𝒫$ and $l \geq 1$ we define $χ_{𝒫, l}^{'} (G)$ to be the minimum number of colours needed to properly colour the edges of $G$ , such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$ . We present a necessary and sufficient condition for the existence of $χ_{𝒫, l}^{'} (G)$ . We focus on edge-colourings of graphs with respect to the hereditary...

Note on improper coloring of $1$ -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph $G = (V, E)$ is called improperly $(d_{1}, \dots, d_{k})$ -colorable if the vertex set $V$ can be partitioned into subsets $V_{1}, \dots, V_{k}$ such that the graph $G [V_{i}]$ induced by the vertices of $V_{i}$ has maximum degree at most $d_{i}$ for all $1 \leq i \leq k$ . In this paper, we mainly study the improper coloring of $1$ -planar graphs and show that $1$ -planar graphs with girth at least $7$ are $(2, 0, 0, 0)$ -colorable.

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu (2024)

Czechoslovak Mathematical Journal

Similarity:

The Turán number of a given graph $H$ , denoted by $ex (n, H)$ , is the maximum number of edges in an $H$ -free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $ex (n, K_{p} \cup K_{q}$ ) of a vertex-disjoint union of cliques $K_{p}$ and $K_{q}$ for all values of $n$ .