Results 21 to 30 of about 4,035 (167)
Applications of hypergraph coloring to coloring graphs not inducing certain trees
Discrete Mathematics, 1996 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.
H. A. Kierstead, V. Rödl
openalex +4 more sources
New hardness results for graph and hypergraph colorings.
, 2016 Finding a proper coloring of a t-colorable graph G with t colors is a classic NP-hard problem when t ≥ 3. In this work, we investigate the approximate coloring problem in which the objective is to find a proper c-coloring of G where c ≥ t. We show that for all t ≥ 3, it is NP-hard to find a c-coloring when c ≤ 2t - 2.
Joshua Brakensiek, Venkatesan Guruswami
+6 more sources
On the Advice Complexity of Coloring Bipartite Graphs and Two-Colorable Hypergraphs
Acta Cybernetica, 2018 Judit Nagy-György
openalex +4 more sources
Some extremal results concerning the number of graph and hypergraph colorings [PDF]
Banach Center Publications, 1989 Ioan Tomescu
openalex +3 more sources
Scheduling Problems and Generalized Graph Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, andsimplicial complexes. To this coloring there is an associated symmetric function in noncommuting variables for whichwe give a deletion-contraction ...
John Machacek
doaj +1 more source
Zero-Free Intervals of Chromatic Polynomials of Mixed Hypergraphs
Mathematics, 2022 A mixed hypergraph H is a triple (X,C,D), where X is a finite set and each of C and D is a family of subsets of X. For any positive integer λ, a proper λ-coloring of H is an assignment of λ colors to vertices in H such that each member in C contains at ...
Ruixue Zhang +2 more
doaj +1 more source
A Theoretical Investigation Based on the Rough Approximations of Hypergraphs
Journal of Mathematics, 2022 Rough sets are a key tool to model uncertainty and vagueness using upper and lower approximations without predefined functions and additional suppositions.
Musavarah Sarwar
doaj +1 more source
Dimension, Graph and Hypergraph Coloring
Order, 2000 A linear extension \(L\) of a poset \(P\) reverses an incomparable pair \((x,y)\) of \(P\) if \(x>y\) in \(L\). A set \(S\) of incomparable pairs forms a strict alternating cycle of \(P\) if no linear extension of \(P\) reverses all pairs in \(S\) but for all \(T \subset S\) there is a linear extension of \(P\) which reverses all pairs in \(T\).
Felsner, Stefan, Trotter, William T.
openaire +4 more sources
Graphs with coloring redundant edges
Electronic Journal of Graph Theory and Applications, 2016 A graph edge is $d$-coloring redundant if the removal of the edge doesnot change the set of $d$-colorings of the graph. Graphs that are toosparse or too dense do not have coloring redundant edges.
Bart Demoen, Phuong-Lan Nguyen
doaj +1 more source
Turán Density of $2$-Edge-Colored Bipartite Graphs with Application on $\{2, 3\}$-Hypergraphs [PDF]
The Electronic Journal of Combinatorics, 2021 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 $
Linyuan Lu, Shuliang Bai
openaire +1 more source