Results 31 to 40 of about 351 (173)
Turán Density of $2$-Edge-Colored Bipartite Graphs with Application on $\{2, 3\}$-Hypergraphs [PDF]
We consider the Turán problems of $2$-edge-colored graphs. A $2$-edge-colored graph $H=(V, E_r, E_b)$ is a triple consisting of the vertex set $V$, the set of red edges $E_r$ and the set of blue edges $E_b$ where $E_r$ and $E_b$ do not have to be disjoint. The Turán density $\pi(H)$ of $H$ is defined to be $\lim_{n\to\infty} \max_{G_n}h_n(G_n)$, where $
Shuliang Bai, Linyuan Lu
openaire +2 more sources
From NMNR-coloring of hypergraphs to homogenous coloring of graphs
An NMNR-coloring of a hypergraph is a coloring of vertices such that in every hyperedge at least two vertices are colored with distinct colors, and at least two vertices are colored with the same color. We prove that every 3 -uniform 3 -regular hypergraph admits an NMNR-coloring with at most 3 colors.
Janicová, Mária +3 more
openaire +3 more sources
On the connectivity threshold for colorings of random graphs and hypergraphs
Let $Ω_q=Ω_q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let $Γ_q$ be the graph with vertex set $Ω_q$ and an edge ${σ,τ\}$ where $σ,τ$ are colorings iff $h(σ,τ)=1$. Here $h(σ,τ)$ is the Hamming distance $|\{v\in V(H):σ(v)\neqτ(v)\}|$.
Anastos, Michael, Frieze, Alan
openaire +5 more sources
On Hypergraph and Graph Isomorphism with Bounded Color Classes [PDF]
Using logspace counting classes we study the computational complexity of hypergraph and graph isomorphism where the vertex sets have bounded color classes for certain specific bounds. We also give a polynomial-time algorithm for hypergraph isomorphism for bounded color classes of arbitrary size.
Vikraman Arvind, Johannes Köbler
openaire +1 more source
Independent sets of maximum weight in apple-free graphs [PDF]
We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs,
Lozin, Vadim V. +2 more
core +1 more source
On Spectral Properties of Graph Coloring, Directed Graphs, and Hypergraphs [PDF]
In this thesis, we study the connections between several characteristics of graphs, including directed graphs, and hypergraphs to the spectra of related matrices.
Kenter, Franklin Hardin Jones
core +1 more source
Reducing hypergraph coloring to clique search [PDF]
It is known that the legal coloring of the nodes of a given graph can be reduced to a clique search problem. This paper generalizes this result for hypergraphs. Namely, we will show how legal coloring of the nodes of a hypergraph can be reduced to clique
Szabó, Sándor, Zavalnij, Bogdan
core +1 more source
Uniform forcing and immune sets in graphs and hypergraphs [PDF]
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/Zero forcing is an iterative coloring process on a graph that has been widely used in such different areas as ...
Fàbrega Canudas, José +5 more
core +1 more source
Applications of hypergraph coloring to coloring graphs not inducing certain trees
The authors present a simple result on coloring hypergraphs and use it to obtain bounds on the chromatic number of graphs which do not induce certain trees. Several open problems are discussed.
Hal A. Kierstead, Vojtech Rödl
openaire +2 more sources
Fault‐Tolerant Mutual‐Visibility: Complexity and Solutions for Grid‐Like Networks
ABSTRACT Networks are often modeled using graphs, and within this setting we introduce the notion of k$$ k $$‐fault‐tolerant mutual visibility. Informally, a set of vertices X⊆V(G)$$ X\subseteq V(G) $$ in a graph G$$ G $$ is a k$$ k $$‐fault‐tolerant mutual‐visibility set (k$$ k $$‐ftmv set) if any two non‐adjacent vertices in X$$ X $$ are connected by
Serafino Cicerone +3 more
wiley +1 more source

