On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

A Linear Heterochromatic Number of Graphs

Let G=(V(G),E(G)) be a multigraph with multiple loops allowed, and V ₀V(G). We define h(G,V ₀) to be the minimum integer k such that for every edge-colouring of G using exactly k colours, all the edges incident with some vertex in V ₀ receive different colours. In this paper we prove that if each xV ₀ is incident to at least two edges of G, then h(G,V ₀)=(G[V ₀])+|E(G)|–|V ₀|+1 where (G[V ₀]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V ₀. Acknowledgments.We thank the referee for suggesting us a short alternative proof of our main theorem.     

On the α-spectra of Uniform Hypergraphs and Its Associated Graphs

For 0 ≤α 1 and a k-uniform hypergraph H, the tensor A_α(H) associated with H is defined as A_α(H) = αD(H) +(1-α)A(H), where D(H) and A(H) are the diagonal tensor of degrees and the adjacency tensor of H, respectively. The α-spectra of H is the set of all eigenvalues of A_α(H) and the α-spectral radius ρ_α(H) is the largest modulus of the elements in the spectrum of A_α(H). In this paper we define the line graph L(H) of a uniform hypergraph H and prove that ρ_α(H) ≤■ρ_α(L(H)) + 1 + α(Δ-1-δ~*/k), where Δ and δ~* are the maximum degree of H and the minimum degree of L(H), respectively. We also generalize some results on α-spectra of G~(k,s), which is obtained from G by blowing up each vertex into an s-set and each edge into a k-set where 1 ≤ s ≤ k/2.     

On the Number of Edges in Geometric Graphs Without Empty Triangles

In this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove: ${{n \choose 2} - O(n \log n) \leq ET(n) \leq {n \choose 2} - \left(n - 2 + \left\lfloor \frac{n}{8} \right\rfloor \right)}$ .     

On the Number of Bases of Bicircular Matroids

Let t(G) be the number of spanning trees of a connected graph G, and let b(G) be the number of bases of the bicircular matroid B(G). In this paper we obtain bounds relating b(G) and t(G), and study in detail the case where G is a complete graph K_n or a complete bipartite graph K_n,m.Received April 25, 2003     

On the Strong Chromatic Number of Random Hypergraphs

Doklady Mathematics - We study the probability threshold for the property of strong colorability with a given number of colors of a random $$k$$ -uniform hypergraph in the binomial model...     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant $\alpha >0$ such that, for any set P of n⩾ 5 points in general position in the plane, a crossing-free geometric graph on P that is chosen uniformly at random contains, in expectation, at least $(\frac{1}{2}+\alpha )M$ edges, where M denotes the number of edges in any triangulation of P. From this we derive (to our knowledge) the first non-trivial upper bound of the form $c^n\cdot \mathsf{tr}(P)$ on the number of crossing-free geometric graphs on P; that is, at most a fixed exponential in n times the number of triangulations of P. (The trivial upper bound of $2^M\cdot \mathsf{tr}(P)$, or $c=2^{M/n}$, follows by taking subsets of edges of each triangulation.) If the convex hull of P is triangular, then $M=3n-6$, and we obtain $c<7.98$.Upper bounds for the number of crossing-free geometric graphs on planar point sets have so far applied the trivial $8^n$ factor to the bound for triangulations; we slightly decrease this bound to $O({343.11}^n)$.     

On the Number of Independent Sets in Simple Hypergraphs

Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.     

Visibility Graphs and Oriented Matroids

Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

Visibility Graphs and Oriented Matroids

   Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ X in $\mathbb{R }^2$ R 2 that is not an axis-aligned rectangle and for any positive integer $k$ k produces a family $\mathcal{F }$ F of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$ X , such that no three sets in $\mathcal{F }$ F pairwise intersect and $\chi (\mathcal{F })>k$ χ ( F ) > k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.     

On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

On Locally Gabriel Geometric Graphs

Let \(P\) be a set of \(n\) points in the plane. A geometric graph \(G\) on \(P\) is said to be locally Gabriel if for every edge \((u,v)\) in \(G\), the Euclidean disk with the segment joining \(u\) and \(v\) as diameter does not contain any points of \(P\) that are neighbors of \(u\) or \(v\) in \(G\). A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any \(n\), there exists LGG with \(\Omega (n^{5/4})\) edges. This improves upon the previous best bound of \(\Omega (n^{1+\frac{1}{\log \log n}})\). (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any \(n\) point set, there exists an independent set of size \(\Omega (\sqrt{n}\log n)\).     

On the Chromatic Number of Graphs

In this paper, the property of a function to be without exceptional family of elements (EFE) is investigated. We show that, for a pseudomonotone operator, the solvability of a complementarity problem is equivalent to the property of the function to be without EFE. Finally, we study the strict feasibility of a complementarity problem making use of the Leray-Schauder alternative and the notion of EFE.     

On the Pfaffian Number of Graphs

In 2006, Norine conjectured that a graph is k-Pfaffian but not ($k-1$)-Pfaffian if and only if k is a power of four [Norine, S., Drawing 4-Pfaffian graphs on the torus, Combinatorica (accepted for publication), http://www.math.princeton.edu/~snorin/papers.html.]. Recently, we presented a graph that is a counter-example to that conjecture [Miranda, A. A. A. and C. L. Lucchesi, Matching signatures and Pfaffian graphs, Technical report, Institute of Computing – University of Campinas – UNICAMP (2009). URL http://www.ic.unicamp.br/~reltech/2009/09-06.pdf]. In this article, we present an alternative proof that this graph is a counter-example to the conjecture. In fact, we present a graph that is not 4-Pfaffian and give a simple proof that it is 10-Pfaffian, using new methods.     

On the Number of Non-Hamiltonian Graphs

In this paper, maximal non-Hamiltonian graphs ( MNH graphs), i.e., non-Hamiltonian graphs such that the addition of any new edge violates their property of being non-Hamiltonian are studied. It is shown that the study of MNH graphs can be reduced to the study of the so-called simplified MNH graphs. Restrictions on the structure of maximal cliques of simplified MNH graphs are obtained, the orders and the number of such graphs are estimated.