Search results for "Edge"

An exact method for graph coloring

2006

International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.

Quasi Conjunction and Inclusion Relation in Probabilistic Default Reasoning

2011

We study the quasi conjunction and the Goodman & Nguyen inclusion relation for conditional events, in the setting of probabilistic default reasoning under coherence. We deepen two recent results given in (Gilio and Sanfilippo, 2010): the first result concerns p-entailment from a family F of conditional events to the quasi conjunction C(S) associated with each nonempty subset S of F; the second result, among other aspects, analyzes the equivalence between p-entailment from F and p-entailment from C(S), where S is some nonempty subset of F. We also characterize p-entailment by some alternative theorems. Finally, we deepen the connections between p-entailment and the Goodman & Nguyen inclusion…

Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

2013

Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …

Logical definability of NP-optimisation problems with monadic auxiliary predicates

1993

Given a first-order formula ϕ with predicate symbols e1...el, so,...,sr, an NP-optimisation problem on -structures can be defined as follows: for every -structure G, a sequence of relations on G is a feasible solution iff satisfies ϕ, and the value of such a solution is defined to be ¦S0¦. In a strong sense, every polynomially bounded NP-optimisation problem has such a representation, however, it is shown here that this is no longer true if the predicates s1, ...,sr are restricted to be monadic. The result is proved by an Ehrenfeucht-Fraisse game and remains true in several more general situations.

Sobolev embeddings, extensions and measure density condition

2008

AbstractThere are two main results in the paper. In the first one, Theorem 1, we prove that if the Sobolev embedding theorem holds in Ω, in any of all the possible cases, then Ω satisfies the measure density condition. The second main result, Theorem 5, provides several characterizations of the Wm,p-extension domains for 1<p<∞. As a corollary we prove that the property of being a W1,p-extension domain, 1<p⩽∞, is invariant under bi-Lipschitz mappings, Theorem 8.

On Coloring Unit Disk Graphs

1998

In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.

Optical Graph Edge Recognition

2018

Heyting-valued interpretations for Constructive Set Theory

2006

AbstractWe define and investigate Heyting-valued interpretations for Constructive Zermelo–Frankel set theory (CZF). These interpretations provide models for CZF that are analogous to Boolean-valued models for ZF and to Heyting-valued models for IZF. Heyting-valued interpretations are defined here using set-generated frames and formal topologies. As applications of Heyting-valued interpretations, we present a relative consistency result and an independence proof.

Highly irregular graphs with extreme numbers of edges

1997

Abstract A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.

A dual of 4-regular graph forG × C2n

2003

Abstract A graph is said h-decomposable if its edge-set is decomposable into edge-disjoint hamiltonian cycles. Jha [3] conjectured that if G is a non-bipartite h-decomposable graph on even number of vertices, then G × K2 is h-decomposable. We use the notion of dual graph defined in [4], we prove that if G = Q1,2 ⊕ C3,4 is a 4-regular non-bipartite h-decomposable graph and the dual graphs relative to Q1,2 and C3,4 are connected then G × K 2 and G × C 2n are h-decomposable (where C 2n is an even cycle).