Record number :

1454636

Title of article :

Θ-graphs of partial cubes and strong edge colorings

Author/Authors :

Kraner ?umenjak، نويسنده , , Tadeja، نويسنده ,

Issue Information :

روزنامه با شماره پیاپی سال 2007

Pages :

6

From page :

521

To page :

526

Abstract :

It was conjectured in [5] that the upper bound for the strong chromatic index s ′ ( G ) of bipartite graphs is Δ ( G ) 2 , where Δ ( G ) is the largest degree of vertices in G. In this note we study the strong edge coloring of some classes of bipartite graphs that belong to the class of partial cubes. We introduce the concept of Θ-graph Θ ( G ) of a partial cube G, and show that s ′ ( G ) ⩽ χ ( Θ ( G ) ) for every tree-like partial cube G. As an application of this bound we derive that s ′ ( G ) ⩽ 2 Δ ( G ) if G is a p-expansion graph.

Keywords :

strong chromatic index , p-expansion graph , Median graph , tree-like partial cube

Journal title :

Electronic Notes in Discrete Mathematics

Journal title :

Electronic Notes in Discrete Mathematics

Serial Year :

2007

Link To Document :