Volume 42 – 2012 – 5th Latin-American Workshop on Cliques in Graphs

The interval count is the smallest number of distint interval lengths over all models of a particular interval graph. Although the graphs having interval count one are well-known since the sixties, very few is known aboutthe graphs having interval count k ≥ 2, even for fixed k. Recently, a polynomial-time algorithm has been presented to compute the interval count of extended-bull-free graphs, letting open the efficient computation of interval count of graphs in which extended-bulls may exist.

Solitaire Clobber is a game played on a graph G by placing a stone, black or white, on each vertex of the graph. We pick up a stone and clobber another one of opposite color located on an adjacent vertex; the clobbered stone is removed from the graph and it is replaced by the picked one.

A graph G is a directed (respectively rooted directed) path graph or a DV (RDV) graph if it admits a DV-model (RDV-model), i.e a clique tree T whose edges can be directed (directed from a root towards the leaves)such thatfor every vertex of G the subtree induced by the cliquesthat contain it is a directed subpath of T. An interval graph is the intersection graph of a family of subpaths of a path.

An AVD-total-colouring of a simple graph G is a mapping φ : V (G) ∪ E(G) → C, with C a set of colours, such that: (i) for each adjacent or incident elements x,y ∈ V (G) ∪ E(G), φ(x) ?= φ(y); (ii) and for each pair of adjacent vertices x,y ∈ V (G), sets {φ(x)}∪ {φ(xv): xv ∈ E(G)} and {φ(y)}∪{φ(yv): yv ∈ E(G)} are distincts. The AVD-total-chromatic number, χ”a(G), is the smallest number of colours for which G admits an AVD-total-colouring.

We survey some recent developments related to three classical lower bounds on the independence number of graphs; Caro’s and Wei’s bound for general graphs, Shearer’s bound for triangle-free graphs, and Staton’s bound for triangle-free graphs of maximum degree at most three. We discuss these bounds, their proofs, and some of our own research that evolved around them.

Let Kr denote the complete graph on r vertices. Given positive integers n1 ≥ 2 and n2 ≥ 2, recall that the celebrated Ramsey number r(n1,n2) denotesthe smallest natural number r such that every red-blue coloring of the edges of Kr yields a red copy of Kn1 or a blue copy of Kn2. Determining Ramsey numbers has been a great challenge in graph theory

A probe graph for a graph class C is a graph G = (V,E),such that it is possible to add some edges between vertices of an independent set N in order to obtain a graph G? belonging to C [7]. If the independent set N c V is given asinput, we have a special case of graph sandwich problem [6], called partitioned probe problem. A graph partition of a graph G = (V,E) is a partition of V into a number of parts