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 :
بازگشت