Home  About us  Contact
 

Graph G. (graph + g)

Distribution by Scientific Domains
Mathematics and Statistics100%

Selected Abstracts

The minimum degree of Ramsey-minimal graphs

JOURNAL OF GRAPH THEORY, Issue 2 2007
Jacob Fox
Abstract We write H,,,G if every 2-coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G - minimal if H,,,G, but for every proper subgraph H, of H, H,,,,,G. We define s(G) to be the minimum s such that there exists a G -minimal graph with a vertex of degree s. We prove that s(Kk),=,(k,,,1)2 and s(Ka,b),=,2 min(a,b),,,1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167,177, 2007 [source]

Improper coloring of unit disk graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2009
Frédéric Havet
Abstract Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is k -improper if no more than k neighbors of every vertex have the same colour as that assigned to the vertex. The k -improper chromatic number ,k(G) is the least number of colors needed in a k -improper coloring of a graph G. The main subject of this work is analyzing the complexity of computing ,k for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing ,k for unit interval graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

What is the furthest graph from a hereditary property?

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008
Noga Alon
Abstract For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of EP(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = EP(G(n,p(P))) + o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

Space complexity of random formulae in resolution

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2003
Eli Ben-Sasson
We study the space complexity of refuting unsatisfiable random k -CNFs in the Resolution proof system. We prove that for , , 1 and any , > 0, with high probability a random k -CNF over n variables and ,n clauses requires resolution clause space of ,(n/,1+,). For constant ,, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density , , n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with ,n clauses requires treelike refutation size of exp(,(n/,1+,)), for any , > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92,109, 2003 [source]