19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Lexicographic products and colourings of graphs

Presented by Ewa DRGAS-BURCHARDT
Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs


Let L denote the class of graphs closed under isomorphism, substitution and taking induced subgraphs. Let P_1, P_2 be in L. We say that a graph G belongs to the class P_1 \ circ P_2 if the vertex set of G can be divided into two subsets V_1, V_2, such that for i \ in {1,2} the graph G [V_i] induced in G by V_i belongs to P_i. Using the theorem proved by Gallai, which concerns the modular decomposition of a graph, we know that every finite simple graph can be uniquely described as composition lexicographic products of prime graphs. In particular, the graphs, that are forbidden for classes P_1\circ P_2, where P_1, P_2 \in L, have such a description. In this talk we study the structure of such graphs showing them as lexicographic products of graphs that are forbidden for P_1 and for P_2. This analysis allows to find a result that the class of minimal forbidden graphs for P_1\circ P_2, where P_1, P_2 \in L, is finite if and only if P_1 is finite and the class of forbidden graphs for P_2 is finite or P_1\circ P_2 is the class of split graphs. This is a partial solution of conjecture, stated in 2002 by Zverovich, which concerns the finiteness of families of forbidden graphs for the class P_1\circ P_2, where both of P_1,P_2 are induced hereditary Our proof confirms this conjecture in L.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors