Star edge coloring of Cactus graphs

arXiv1911.02343MaRDI QIDQ6328652FDOQ6328652

Authors: Behnaz Omoomi, Marzieh Vahid Dastjerdi, Yasaman Yektaeian 

Publication date: 6 November 2019

Abstract: A star edge coloring of a graph $G$ is a proper edge coloring of $G$ such that no path or cycle of length four is bi-colored. The star chromatic index of $G$, denoted by $ch{i}_s^{prime}(G)$, is the minimum $k$ such that $G$ admits a star edge coloring with $k$ colors. Bezegov{'a} et al. (Star edge coloring of some classes of graphs, J. Graph Theory, 81(1), pp.73-82. 2016) conjectured that the star chromatic index of outerplanar graphs with maximum degree $Delta$, is at most $leftlfloorfrac3Delta2ightfloor+1$. In this paper, we prove this conjecture for a class of outerplanar graphs, namely Cactus graphs, wherein every edge belongs to at most one cycle.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Star edge coloring of Cactus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328652)