Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

On acyclic colorings of direct products

Simon Špacapan;  Aleksandra Tepeh Horvat — 2008

Discussiones Mathematicae Graph Theory

A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.

The periphery graph of a median graph

Boštjan Brešar;  Manoj Changat;  Ajitha R. Subhamathi;  Aleksandra Tepeh — 2010

Discussiones Mathematicae Graph Theory

The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like...

Page 1

Download Results (CSV)