Results 41 to 50 of about 238 (165)
Homomorphisms of complete n-partite graphs
International Journal of Mathematics and Mathematical Sciences, 1986 It is shown that for every homomorphism ϕ of a graph G there exists a contraction θϕ on G¯, the complement of G, such that ϕ(G)¯=θϕ(G¯) if and only if G is a complete n-partite graph.
Robert D. Girse
doaj +1 more source
Novel Concepts in Bipolar Fuzzy Graphs with Applications
Journal of Mathematics, 2022 Many problems of practical interest can be modeled and solved by using bipolar graph algorithms. Bipolar fuzzy graph (BFG), belonging to fuzzy graphs (FGs) family, has good capabilities when facing with problems that cannot be expressed by FGs. Hence, in
Chang Wan +5 more
doaj +1 more source
Forum of Mathematics, PiAbstract We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the construction comes from the adaptation of this method to the $\mathsf {LOCAL}$
Sebastian Brandt +5 more
openaire +6 more sources
Homomorphisms and polynomial invariants of graphs
European Journal of Combinatorics, 2007 Junta de Andalucía P06-FQM ...
Delia Garijo +2 more
openaire +5 more sources
Spectral Independence via Stability and Applications to Holant-Type Problems [PDF]
TheoretiCSThis paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then ...
Zongchen Chen, Kuikui Liu, Eric Vigoda
doaj +1 more source
Oriented Incidence Colourings of Digraphs
Discussiones Mathematicae Graph Theory, 2019 Brualdi and Quinn Massey [6] defined incidence colouring while study- ing the strong edge chromatic index of bipartite graphs. Here we introduce a similar concept for digraphs and define the oriented incidence chromatic number.
Duffy Christopher +3 more
doaj +1 more source
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability [PDF]
TheoretiCSWe show that feasibility of the $t^\text{th}$ level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation.
David E. Roberson, Tim Seppelt
doaj +1 more source
Chromatic Ramsey Numbers and Two‐Color Turán Densities
Journal of Graph Theory, EarlyView.ABSTRACT Given a graph G, its 2‐color Turán number ex ( 2 ) ( n , G ) is the maximum number of edges in an n‐vertex graph, such that the edges can be colored with two colors avoiding a monochromatic copy of G. Let π ( 2 ) ( G ) = lim n → ∞ ex ( 2 ) ( n , G ) / n 2 be the 2‐color Turán density of G.
Maria Axenovich, Simon Gaa, Dingyuan Liu
wiley +1 more source
Explicit 3‐colorings for Exponential Graphs
Journal of Graph Theory, EarlyView.ABSTRACT In 1985, El‐Zahar and Sauer showed that the chromatic number of the direct product of two 4‐chromatic graphs is 4, establishing a nontrivial case of Hedetniemi's conjecture, which has since been refuted in general. Their proof uses the concept of an exponential graph, showing that if a graph H $H$ has no proper 3‐coloring, then the exponential
Adrien Argento +2 more
wiley +1 more source
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability [PDF]
QuantumMančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al.
Prem Nigam Kar +3 more
doaj +1 more source