On Color Critical Graphs of Star Coloring

MaRDI QIDQ6438316zbMATH OpenFDO

Authors Harshit Kumar Choudhary, I. Vinod Reddy

Publication date 29 May 2023

Abstract: A emph{star coloring} of a graph $G$ is a proper vertex-coloring such that no path on four vertices is $2$-colored. The minimum number of colors required to obtain a star coloring of a graph $G$ is called star chromatic number and it is denoted by $ch{i}_s(G)$. A graph $G$ is called $k$-critical if $ch{i}_s(G)=k$ and $ch{i}_s(G-e)<ch{i}_s(G)$ for every edge $einE(G)$. In this paper, we give a characterization of 3-critical, $(n-1)$-critical and $(n-2)$-critical graphs with respect to star coloring, where $n$ denotes the number of vertices of $G$. We also give upper and lower bounds on the minimum number of edges in $(n-1)$-critical and $(n-2)$-critical graphs.

This page was built for publication: On Color Critical Graphs of Star Coloring

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