Clique covering of graphs

Let cc(G) denote the least number of complete subgraphs necessary to cover the edges of a graphG. Erd?s conjectured that for a graphG onn vertices $$cc(G) + cc(\bar G) \leqq \frac{1}{4}n^2 + 2$$ ifn is sufficiently large. We prove this conjecture.     

Clique coloring of dense random graphs

The clique chromatic number of a graph is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph is, with high probability, . This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is with high probability.     

Clique coloring of binomial random graphs

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.     

Clique or hole in claw-free graphs

Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y. We derive two applications: We give a necessary and sufficient condition for the existence of an induced x-z path through y, where x,y,z are prescribed vertices in a claw-free graph; and we prove an induced version of Menger?s theorem between four terminal vertices. Finally, we improve the running time for detecting a hole through x and y and for the Three-in-a-Tree problem, if the input graph is claw-free.     

Clique coverings and partitions of line graphs

A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem.     

Clique number of Xor products of Kneser graphs

In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on k, and find the exact value for $f(2,N)$ if N is large enough. Also we compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.     

Clique detection in directed graphs: a new algorithm

A new algorithm for clique-detection in a graph is introduced. The method rests on the so-called “decomposition of a graph into a chain of subgraphs” and on the corresponding so-called “quasi-blockdiagonalisation” of the adjacency matrix. A FORTRAN IV computer-program is presented.     

Clique partitions of complements of forests and bounded degree graphs

In this paper, we prove that for any forest F⊂K_n, the edges of E(K_n)?E(F) can be partitioned into O(nlogn) cliques. This extends earlier results on clique partitions of the complement of a perfect matching and of a hamiltonian path in K_n.In the second part of the paper, we show that for n sufficiently large and any ε∈(0,1], if a graph G has maximum degree O(n^1-ε), then the edges of E(K_n)?E(G) can be partitioned into cliques provided there exist certain Steiner systems. Furthermore, we show that there are such graphs G for which Ω(ε²n^2-2ε) cliques are required in every clique partition of E(K_n)?E(G).     

Clique trees of chordal graphs: leafage and 3-asteroidals

Chordal graphs were characterized as those graphs having a tree, called clique tree, whose vertices are the cliques of the graph and for every vertex in the graph, the set of cliques that contain it form a subtree of clique tree. In this work, we study the relationship between the clique trees of a chordal graph and its subgraphs. We will prove that clique trees can be described locally and all clique trees of a graph can be obtained from clique trees of subgraphs. In particular, we study the leafage of chordal graphs, that is the minimum number of leaves among the clique trees of the graph. It is known that interval graphs are chordal graphs without 3-asteroidals. We will prove a generalization of this result using the framework developed in the present article. We prove that in a clique tree that realizes the leafage, for every vertex of degree at least 3, and every choice of 3 branches incident to it, there is a 3−asteroidal in these branches.     

On time graphs

For n points on the real line, joining each pair of points such that their difference is less than a certain positive constant, we have a time graph. In this paper we characterize time graphs and enumerate them.     

The infection time of graphs

Consider k particles, 1 red and k-1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it “infects” it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k-1 to the white ones. The infection timeT_k of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph.In this work we develop a set of probabilistic tools that we use to obtain upper bounds on the (worst case w.r.t. initial positions of particles) expected value of T_k for general graphs and important special cases. We easily get that an upper bound on the expected value of T_k is the worst case (over all initial positions) expected meeting timem^* of two random walks multiplied by . We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the “lollipop” graph), a range of values k<n (such that ) and an initial position of particles achieving this bound.When G is a clique or has nice expansion properties, we prove much smaller bounds for T_k. We have evaluated and validated all our results by large scale experiments which we also present and discuss here. In particular, the experiments demonstrate that our analytical results for these expander graphs are tight.     

Coloring Meyniel graphs in linear time

A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. We present a linear-time algorithm that colors optimally the vertices of a Meyniel graph and finds a clique of maximum size.     

Clique percolation

Derényi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph Ggenerated by some rule, form an auxiliary graph G′ whose vertices are the k‐cliques of G, in which two vertices are joined if the corresponding cliques share k – 1 vertices. They considered in particular the case where G = G(n,p), and found heuristically the threshold function p = p(n) above which a giant component appears in G′. Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in G′. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The cover time of random geometric graphs

We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r. Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x. The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G. Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011