Star Edge Coloring And 2-Distance Vertex Distinguishing Edge Coloring Of Graphs

This thesis is devoted to the study of two graph colouring problems.The first is the star edge coloring problem,which aims to find the smallest number of colors ?'_st?the star chromatic index?that suffices to color the edges of a graph such that any two adjacent edges have different colors and there is no bi-colored path or cycle of length four.The second problem which constitute the main topic of the the-sis,is the 2-distance vertex distinguishing edge coloring problem or 2DVDE coloring problem.The latter problem is to estimate the minimum number of colors ?'_d2?the 2DVDE index?,required for a proper edge coloring of a graph,such that any pair of vertices at distance two have distinct sets of colors on their incident edges.The star edge coloring problem,introduced by Liu and Deng?2008?,has attracted lots of attention and is considered very hard,even for the characterization of graphs for which this invariant is equal to three;In the same vein,we know very little about the star chromatic index of complete graphs.On the other hand,the 2DVDE coloring problem was recently defined by Wang et al.?2016a?,who also conjectured that every graph G with maximum degree ? has ?'_d2?G???+2.This problem belongs to the well-studied family of difficult problems known as vertex distinguishing colorings.These coloring problems have applications in network optimization.Our work is organized into two main parts.In the first part of the thesis,we give in Chapter 2,a formal presentation of the star edge coloring problem and related woks on this topic.Then,in the third chap?ter,we focus our investigation on the star chromatic index of complete bipartite graphs K_m,n through a constructive approach and derive bounds for ?'_st?K_n,n?and ?'_st?K_n?.In particular,describe a recursive procedure to star edge colored K_n,n and K_n in O(n^log?3?).This study is partially motivated by the fact that there exists a relationship between the star chromatic index of the complete graph K?+1 and the star chromatic index of an arbitrary graph of maximum degree ?,as shown by Dvo??????k,Mohar,and ??????mal?2013?.The second part is dedicated to the study of 2DVDE coloring of several fami-lies of graphs.Chapter 4 introduces 2DVDE coloring and vertex distinguishing edge colorings in general,together with the related main results.Then in the fifth chapter,we prove the existence of an infinite family of graphs for which the conjecture above does not hold.In addition,we establish the NP-completeness of determining whether an arbitrary graph admits a 2DVDE coloring with three colors.Furthermore,we obtain linear upper bounds for planar graphs and sub-families of planar graphs and estimate ?'_d2 for the Cartesian product of paths and arbitrary graphs.In the sixth chapter,we prove that at most six colors are enough to provide a 2DVDE coloring to every subcubic graph,and conjecture that the optimal bound on this family may be five colors.In the following chapter,we partially confirm this conjecture for subcubic graphs with maximum average de-gree?mad?less than 8/3.Finally,in the last chapter,we prove that every sparse graph G with mad?G?<5/2?resp.mad?G?<8/3?,satisfies ?'_d2?G????G?+2(resp.?'_d2?G????G?+3).