## Articles

### 5th Latin-American Workshop on Cliques in Graphs – Prefácio

Authors:Celina M. H. de Figueiredo, Marina Groshaus, Fábio Protti, Francisco Soulignac

### Interval Count of Generalizations of Threshold 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 ﬁxed k. Recently, a polynomial-time algorithm has been presented to compute the interval count of extended-bull-free graphs, letting open the eﬃcient computation of interval count of graphs in which extended-bulls may exist.

Authors:M. R. Cerioli, F. de S. Oliveira, J. L. Szwarcﬁter

### Strong reducibility of Solitaire Clobber played on Cartesian product of graphs

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.

Authors:Simone Dantas, Sylvain Gravier, Telma Pará

### DV-model that can be rooted

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.

Authors:Marisa Gutierrez, Silvia B Tondato

### AVD-total-colouring of complete equipartite graphs

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.

Authors:A. G. Luiz, C. N. Campos, C. P. de Mello

### Independence in Graphs A Medley of Popular Tunes

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.

Authors:Dieter Rautenbach

### Multicolored Ramsey Numbers in Multipartite Graphs

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

Authors:Juliana Sanches, E.L. Monte Carmelo

### Searching for a NP-Complete Probe Graph Problem

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

Authors:R. B. Teixeira, C. M. H. de Figueiredo, S. Dantas

### EPT graphs on bounded degree trees

An undirected graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. In this paper, we answer negatively the question posed by Golumbic et al. [4]: Can any EPT graph without induced cycles of size greater than h be represented in a host tree with maximum degree h?

Authors:Liliana Alcón, Marisa Gutierrez, María Pía Mazzoleni

### Sandwich Problems: why not ask for special kinds of bread?

In this work, we consider the Golumbic, Kaplan, and Shamir decision sandwich problem for a property II:given two graphs G1 = (V,E1) and G2 = (V,E2), the question is: Is there a graph G = (V,E) such that E1 c E c E2 and G satisfies II? The graph G is called sandwich graph. Note that what matters here is just the “filling” of the sandwich.

Authors:F. Couto, L. Faria, S. Klein, F. Protti, L. T. Nogueira

### Design of connection networks with bounded number of non-terminal vertices

The spanning tree problem and the steiner tree problem aim at obtaining an acyclic subgraph connecting a set of terminal points and satisfying some properties. Both problems have several important network applications.

Authors:Mitre C. Dourado, Rodolfo A. Oliveira, Fábio Protti, Uéverton S. Souza

### Characterizing Clique Graphs of Chordal Comparability Graphs

The clique graph K(G) of a graph G is the intersection graph of the maximal cliques of G. A well-known characterization of clique graphs is that by Roberts and Spencer (1971). In addition there are characterizations for clique graphs of several graph classes.

Authors:Michel Habib, Denis Julien, Ross M. McConnell, Vin´ıcius F. dos Santos

### Integer index of p-broom-like graphs

A p-broom-like graph is obtained by identifying each vertex of a p-clique with the root of a copy of a rooted broom. We prove that the class of p-broom-like graphs with n vertices is total and strictly ordered by the index (the largest eigenvalue ofthe adjacency matrix). Moreover, for p-broom-like maximal graphs (higher index) we obtain integrality conditions, both for the index as for the graph itself, proving the existence of an integral p-broom-like graph for each p-clique with p ≥ 5.

Authors:Laura Patuzzi, Maria Aguieiras A. de Freitas, Renata R. Del-Vecchio

### Two Families of Cayley Graph Interconnection Networks

The family Hl,p has been deﬁned in the context of edge partitions, and subsequently shown to be composed by Hamiltonian Cayley graphs. The pl−1 vertices of the graph Hl,p are the l-tuples with values between 0 and p − 1, such that the sum of the l values is congruent to 0 mod p, and there is an edge between two vertices having two corresponding pairs of entries whose values differ by one unit.

Authors:André da C. Ribeiro, Luis Antonio B. Kowada, Celina M. H. de Figueiredo

### Total chromatic number of some families of graphs with maximum degree 3

The focus of this work is the total coloring of graphs with maximum degree 3. We 4-total-color ﬁve inﬁnite families with maximum degree 3: a new inﬁnite family of snarks constructed from Blanusa snarks; two new inﬁnite families of cubic graphs constructed from 4-Möbius-ladder and 5-ladder, respectively; and two grid families,Hexagonal-grid and Pentagonal-grid.

Authors:D. Sasaki, S. Dantas, C. M. H. de Figueiredo, M. Preissmann