Upper Bound for Star Chromatic Number

I.D Hettiarachchi, A.M.C.U.M Athapattu

Department of Mathematics, Faculty of Science, University of Peradeniya, Sri Lanka

DOI: https://doi.org/10.51244/IJRSI.2024.1106041

Received: 03 June 2024; Accepted: 15 June 2024; Published: 19 July 2024

ABSTRACT

Star coloring of an undirected graph \( G \) is a proper vertex coloring such that any path of length 3 in \( G \) is not bicolored and the notion of star chromatic number implies the minimum number of colors needed to star coloring of \( G \). In this paper we explore the concept of star coloring star chromatic number and a powerful probabilistic lemma known as the Lovasz Local Lemma and establish an improved upper bound for the star chromatic number which is \( \left\lceil 6 \sqrt[3]{d} \right\rceil \) where \( d \) is the maximum degree of the graph.

Keywords: Star coloring, Star chromatic number, Proper vertex coloring, Lovasz Local Lemma

INTRODUCTION

Graph theory is a branch of mathematics that explores the relationships and connections between objects. These objects represented as vertices or nodes are connected by edges. In graph theory, graph coloring is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called vertex coloring. Similarly, edge coloring and face coloring are defined.

Star coloring is a concept that extends the notion of vertex coloring by adding an additional constraint. In 1973, the concept of star coloring and the notion of star chromatic number \( \chi_s(G) \) were introduced by Branko Grunbaum [5]. After that, star coloring and star chromatic number of graphs have been studied extensively by several authors. Some of them have introduced values for the star chromatic number of some types of graphs such as:

1. Cycle Graphs (\( n \ge 3 \)) = {4 if \( n = 5 \), 3 otherwise [8]
2. Complete Graphs (\( n \ge 3 \)) = \( n \) [8]
3. Path Graphs (\( n \ge 4 \)) = 3 [8]

As well as over the years numerous studies have been conducted introducing upper bounds for the star chromatic number. In 2004, Albertson, Chappell, Kierstead, Kundgen, and Ramamurth [1] introduced the upper bound which is \( d^2 – d + 2 \). In 2003, Guillaume Fertin, Andre Raspaud, and Bruce Reed [3] proved that for any graph of order \( n \) and maximum degree \( d \), \( \chi_s(G) \le \left\lceil 20 \sqrt[3]{d} \right\rceil \). In 2010, Hong Yong Fu and De Zheng Xie [10] decreased the above upper bound furthermore and introduced a new upper bound which is \( \chi_s(G) \le \left\lceil 7 \sqrt[3]{d} \right\rceil \). Both of these two proofs rely heavily on a probabilistic lemma called Lovasz Local Lemma. In this paper, we extend those above results with the help of Lovasz Local Lemma and give a better upper bound for \( \chi_s(G) \), i.e., we show that if \( G \) is a graph with maximum degree \( d \) then \( \chi_s(G) \le \left\lceil 6 \sqrt[3]{d} \right\rceil \).

Definition 1.1 (Path): Let \( G = (V, E) \) be a graph. A walk is an alternating sequence of vertices and edges in \( V \) and \( E \). A path is a walk with no repeated edges and vertices.

Definition 1.2 (Proper Vertex Coloring) [8]: A proper vertex coloring of a graph is a mapping \( c : V(G) \rightarrow \{1, 2, 3, \ldots, k\} \) (\( \{1, 2, 3, \ldots, k\} \) denotes the set of colors) such that \( c(u) \neq c(v) \) for all arbitrary adjacent vertices \( u, v \in V(G) \).

Definition 1.3 (Chromatic Number) [8]: If \( G \) has a proper vertex coloring then the chromatic number of \( G \) is the minimum number of colors needed to color \( G \).

STAR COLORING AND STAR CHROMATIC NUMBER

A. Star Coloring

In star coloring theme, every path involving four vertices necessitates the use of at least three different colors. Alternatively, in the context of star coloring, the subgraphs induced by vertices of any two distinct colors exhibit connected components that manifest as star graphs.

Definition 2.1 (Star Coloring) [8]: A star coloring of a graph \( G \) is a proper vertex coloring of \( G \) such that no path of length 3 in \( G \) is bicolored.

B. Star Chromatic Number

The star chromatic number of an undirected graph \( G \), denoted by \( \chi_s(G) \), is the smallest integer \( k \) for which \( G \) admits a star coloring with \( k \) colors. Computing the star chromatic number for a graph can be a challenging problem and finding an optimal algorithm for it is an active area of research in graph theory.

Definition 2.2 (Star Chromatic Number) [8]: The star chromatic number is the minimum number of colors needed for star color \( G \).

LOVASZ LOCAL LEMMA

The Lovasz Local Lemma was introduced by Erdos and Lovasz in 1975 [2], who used it in their article about hypergraph coloring. The Lovasz Local Lemma is a probabilistic method of proving the existence of a specific object without showing how it looks like.

The Lovasz Local Lemma states that if we have a set of events in which each of them occurs with probability \( p \in (0, 1) \) and is mutually independent of the others with the exception of a few, then there is a nonzero probability that none of the events will occur. Here are the main notable versions of the Lovasz Local Lemma.

1. Symmetric Lovasz Local Lemma
2. Asymmetric Lovasz Local Lemma

A. Symmetric Lovasz Local Lemma

The symmetric version of the Lovasz Local Lemma deals with a situation where all events are considered equally. This version was first introduced by Erdos and Lovasz.

Theorem 3.1 (Symmetric Lovasz Local Lemma) [9]: Suppose \( p \in (0, 1) \), \( d \ge 1 \), and \( U_1, U_2, \ldots, U_n \) are events such that \( P[U_i] \le p \) for all \( i \). If each \( U_i \) is mutually independent of all but \( d \) other events \( U_j \), if
\[
e p (d + 1) \le 1
\]
where \( e = 2.71828 \ldots \) is Euler’s number, then
\[
Pr\left[ \bigcap_{i=1}^n \overline{U_i} \right] > 0
\]

B. Asymmetric Lovasz Local Lemma

The asymmetric version of the Lovasz Local Lemma allows for a more flexible treatment of events. Unlike the symmetric version, it acknowledges that events may have different levels of importance or impact. First we need to define a structure which describes a dependency of events in a probability space.

Definition 3.1 (Dependency Graph). A directed graph \( G’ = (V(G’), E(G’)) \) is a dependency (di) graph on events \( U_i \), where \( i \in V(G’) \) and each event \( U_i \) is mutually independent of its non-neighbors.

Theorem 3.2 (Asymmetric Lovasz Local Lemma).[2] Suppose \( G’ \) is a dependency graph for events \( U_i \) and there exists \( x_i \in (0,1) \) such that
\[
\Pr[U_i] \leq x_i \prod_{(i,j) \in E(G’)} (1 – x_j) \text{ for all } i \in V(G’)
\]
Then,
\[
\Pr\left[ \bigcap_{i=1}^n \overline{U_i} \right] \geq \prod_{i=1}^n (1 – x_i) > 0.
\]

C. Applications of Lovasz Local Lemma

1) Lower bound for Ramsey numbers R(3, l) \([4]\); Using the asymmetric version of LLL following lower bound can be obtained.

\[ R(k,l) \leq \binom{k+l-2}{k-1} \]

2) An application of frugal graph coloring [7]; i.e If graph \( G \) has maximum degree β^β then \( G \) has a \( \beta \)-frugal coloring with \( 16d^{1+\frac{1}{\beta}} \) colors.

3) Existence of a satisfying k-SAT assignment [6]; i.e Any instance \( \phi \) of \( k \)-SAT in which no variable appears in more than \( 2^{k-2k} \) clauses is satisfiable. Here we can prove that probability of picking an assignment that satisfies every clause in \( \phi \) is non-zero then using LLL result can be obtained.

4) Packet Routing in Networks [6]; i.e In each phase of length \( \log d \) there exists a set of delays for the packets so that the max congestion over any edge is at most \( \log d \). Using the asymmetric version of LLL the result can be obtained.

RESULTS

We use the following lemmas to obtain the new upper bound.

Lemma 4.1. [3] Let \( G \) be a graph of maximum degree \( d \) and \( v \) be any vertex of \( G \) then

1. \( v \) belongs to at most \( d \) edges of \( G \).
2. \( v \) belongs to at most \( 2d^3 \) paths of length 3 in \( G \).

Proof :

1. Since maximum degree is \( d \) clearly \( v \) belongs to at most \( d \) edges of \( G \).

2. Let \( v \) be a terminal point of a path of length 3. Then there are \( d \) ways to choose neighboring vertices and \( (d – 1)^2 \) ways to choose paths with length 3 which includes \( v \) as an internal point. Altogether there are \( d(d – 1)^2 \) number of ways to choose paths with length 3 which includes \( v \). Now assume that \( v \) is an internal vertex of path of length 3. Then one of its adjacent vertices \( u \) should be an end point of the path. Since the maximum degree is \( d \) there are \( d \) ways to choose \( u \) and there are \( (d – 1)^2 \) ways to choose paths with length 3 going through \( v \) and \( u \) is an end point. Hence as previously there are \( d(d – 1)^2 \) number of paths of length 3 in \( G \). i.e \( v \) belongs to at most \( 2d(d – 1)^2 \) paths of length 3 in \( G \). Since \( 2d(d – 1)^2 \leq 2d^3 \) \( v \) belongs to at most \( 2d^3 \) paths of length 3 in \( G \).

Lemma 4.2. [3] For \( i, j \in \{I, II\} \) \( A_{ij} \) is an upper bound on the number of vertices of type \( j \) which are adjacent to a vertex of type \( i \) in the dependency graph \( G’ \). Then

1. \( A_{I,I} = 2d \)
2. \( A_{II,I} = 4d \)
3. \( A_{I,II} = 4d^3 \)
4. \( A_{II,II} = 8d^3 \)

Proof :

1. Let \( v_1 \) be a vertex of type I in \( G’ \). \( v_1 \) corresponds to an event \( U_{xy} \) which implies \( x, y \in G \). Thus \( v_1 \) is connected to all the vertices that correspond to events \( U_{xa} \) and \( U_{yb} \) for all the vertices \( a \) that are neighbors of \( x \) and all the vertices \( b \) that are neighbors of \( y \). Hence by the lemma 4.1 there are at most \( d \) vertices that are neighbors of \( x \) in \( G \) and at most \( d \) vertices that are neighbors of \( y \). Therefore \( A_{II} \) is equal to \( 2d \).

2. Let \( v_2 \) be a vertex of type II in \( G’ \). \( v_2 \) corresponds to an event \( V_{wxyz} \) which implies \( w, x, y, z \in G \). \( v_2 \) is connected to all the vertices in \( G’ \) that correspond to events \( U_{wa}, U_{xb}, U_{yc} \) and \( U_{zd} \) where \( a, b, c, d \) are adjacent vertices of \( w, x, y, z \) respectively. By lemma 4.1 there are at most \( d \) vertices that are neighbors of \( w \) in \( G \) as well as \( x, y, z \) in \( G \). Therefore \( A_{III} \) is equal to \( 4d \).

3. Let \( v_1 \) be a vertex of type I in \( G’ \). \( v_1 \) corresponds to an event \( U_{xy} \) which implies \( x, y \in G \). Then \( v_1 \) is connected to all the vertices in \( G’ \) which corresponds to the events of type II which includes \( x \) or \( y \) as a vertex of the path of length 3. Then by lemma 4.1 \( A_{III} \) is equal to \( 4d^3 \).

4. Let \( v_2 \) be a vertex of type II in \( G’ \). \( v_2 \) corresponds to an event \( V_{wxyz} \) which implies \( w, x, y, z \in G \). Then \( v_2 \) is connected to all the vertices in \( G’ \) which corresponds to the events of type II which includes \( w, x, y, z \) as a vertex of a path of length 3. Therefore \( A_{IIII} \) is equal to \( 8d^3 \).

Lemma 4.3. [1] If \( G \) is a graph with maximum degree \( d \) then \( X_{SG} \leq d^2 – d + 2 \).

In this section we introduce the new upper bound.

Theorem 4.1. Let \( G \) be a graph of maximum degree \( d \) then

\[ X_{SG} \leq \left\lceil 6d^{3/2} \right\rceil \]

Proof : In the proof let’s examine two distinct cases for consideration.

Case 1 : when \( d > 36 \)

To apply Lovasz Local Lemma let us define a coloring application for graph \( G \). Define this application as \( f \). \( f \) is a vertex coloring which uses \( \Gamma = \left\lceil 6d^{3/2} \right\rceil \) number of colors randomly and independently according to a uniform distribution on \( \{1, 2, 3, …, \Gamma\} \). And coloring of vertex \( x \) is denoted as \( f(x) \). If \( f \) is a star coloring of \( G \) then \( \Gamma \) is an upper bound for the star chromatic number and the theorem will be proved. i.e we must prove that with non zero probability \( f \) is a star coloring. For this we define family of events on which we apply Lovasz Local Lem

ma. Since Lovasz Local Lemma proves that none of these events occur we have to choose complements of the conditions of star coloring as the events. Then by the Lovasz Local Lemma we can prove that with the non zero probability \( f \) is a star coloring.

Events are as follows.

Type I : For each pair of adjacent vertices \( x \) and \( y \) in \( G \) let \( U_{xy} \) be the event \( f(x) = f(y) \).

Type II: For each path of length 3 \( wxyz \) in \( G \) let \( V_{wxyz} \) be the event \( f(w) = f(y) \) and \( f(x) = f(z) \).

Let us construct a dependency graph \( G’ \) whose nodes are all the events of the two types. And two nodes \( A_X \) and \( B_Y \) where \( A, B \in \{U, V \} \) are adjacent iff \( X \cap Y \neq \emptyset \). Since the occurrence of each event \( A_X \) depends only on the color of the vertices in \( X \) \( G’ \) is a dependency graph for these events because even if the colours of all vertices of \( G \) but those in \( X \) are known the probability of \( A_X \) remains unchanged. Now if a vertex of \( G’ \) corresponds to an event of type i then it will be said to be type \( i \in \{I, II\} \).

Let us consider the following lemma to obtain the degree of each vertex in \( G’ \).

Since we use \( \Gamma \) number of colors for coloring \( f \) we can observe following observation using basic probability concepts.

Observation 4.1.

1. For each Event \( U \) of type I \( \Pr(U) = \frac{1}{\Gamma} \)
2. For each Event \( V \) of type II \( \Pr(V) = \frac{1}{\Gamma} \times \frac{1}{\Gamma} = \frac{1}{\Gamma^2} \)

Now choose \( x_i = \left(\sqrt{\frac{2}{\Gamma}}\right)^i \) where \( i \in \{1, 2\} \). To apply Lovasz Local Lemma we must show that

\[ \Pr(U) = \frac{1}{\Gamma} \leq \frac{\sqrt{2}}{\Gamma} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{2d} \left(1 – \frac{2}{\Gamma^2}\right)^{4d^3} \quad \text{—(1)} \]

\[ \Pr(V) = \frac{1}{\Gamma^2} \leq \frac{2}{\Gamma^2} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{4d} \left(1 – \frac{2}{\Gamma^2}\right)^{8d^3} \quad \text{—(2)} \]

Consider equation (1),

\[ \frac{1}{\Gamma} \leq \frac{\sqrt{2}}{\Gamma} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{2d} \left(1 – \frac{2}{\Gamma^2}\right)^{4d^3} \]

\[ \frac{1}{\sqrt{2}} \leq \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{2d} \left(1 – \frac{2}{\Gamma^2}\right)^{4d^3} \]

Let,

\[ \alpha = \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{2d} \left(1 – \frac{2}{\Gamma^2}\right)^{4d^3} \]

Since \(\Gamma = \lceil 6d^{3/2} \rceil\),

\[ \alpha \geq \left(1 – \frac{\sqrt{2}}{6d^{3/2}}\right)^{2d} \left(1 – \frac{2}{36d^3}\right)^{4d^3} \]

\[ \alpha \geq \frac{1}{\sqrt{2}} \]

for any \( d \geq 15 \).

i.e ,

\[ \Pr(U) = \frac{1}{\Gamma} \leq \frac{\sqrt{2}}{\Gamma} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{2d} \left(1 – \frac{2}{\Gamma^2}\right)^{4d^3} \]

for any \( d \geq 15 \).

Now consider equation (2),

\[ \frac{1}{\Gamma^2} \leq \frac{2}{\Gamma^2} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{4d} \left(1 – \frac{2}{\Gamma^2}\right)^{8d^3} \]

\[ \frac{1}{2} \leq \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{4d} \left(1 – \frac{2}{\Gamma^2}\right)^{8d^3} \]

Let,

\[ \beta = \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{4d} \left(1 – \frac{2}{\Gamma^2}\right)^{8d^3} \]

Since \(\Gamma = \lceil 6d^{3/2} \rceil\),

\[ \beta \geq \left(1 – \frac{\sqrt{2}}{6d^{3/2}}\right)^{4d} \left(1 – \frac{2}{36d^3}\right)^{8d^3} \]

\[ \beta \geq \frac{1}{2} \]

for any \( d \geq 15 \).

i.e ,

\[ \Pr(V) = \frac{1}{\Gamma^2} \leq \frac{2}{\Gamma^2} \left(1 – \frac{\sqrt{2}}{\Gamma}\right)^{4d} \left(1 – \frac{2}{\Gamma^2}\right)^{8d^3} \]

for any d ≥ 15.

Hence equations (1) and (2) satisfy for any \( d > 36 \). Then by Lovasz Local Lemma we can obtain

\[\Pr\left(\bigcap_{i=1}^n\overline{U_i}\right) \geq \prod_{i=1}^n (1 – x_i) > 0.\]

\[\Pr\left(\bigcap_{i=1}^n\overline{ V_i}\right) \geq \prod_{i=1}^n (1 – x_i) > 0.\]

Therefore we can conclude that for any \( d > 36 \) \( f \) is a star coloring.

i.e \( \Gamma = \left\lceil 6d^{3/2} \right\rceil \) is an upper bound for star chromatic number.

i.e for any \( d > 36 \) \( X_{SG} \leq \left\lceil 6d^{3/2} \right\rceil \) —(3)

Case 2: When \(d \leq 36\)

Since \(d \leq 36\),

\[1 \leq \frac{36}{d}\]

\[1 \leq \frac{6}{\sqrt{d}}\]

Clearly,

\[d^2 – d + 2 \leq d^2 \quad (\text{since } d \geq 2)\]

\[d^2 – d + 2 \leq d^2 \times \frac{6}{\sqrt{d}} \quad (\text{since } 1 \leq \frac{6}{\sqrt{d}})\]

\[d^2 – d + 2 \leq 6d^{3/2}\]

By Lemma 4.3,

\[X_S(G) \leq 6d^{3/2}\]

i.e., for any \(d \leq 36\),

\[X_S(G) \leq \lceil 6d^{3/2} \rceil \quad \text{—(4)}\]

Therefore, by equations (3) and (4), for every \(d\),

\[X_S(G) \leq \lceil 6d^{3/2} \rceil\]

∎

CONCLUSION

The central focus of this research is explore the star chromatic number and obtain a new upper bound for star chromatic number. Through rigorous mathematical analysis and application of Lovasz Local Lemma, we have proven that star chromatic number is bounded above by \( \left\lceil 6 \sqrt[3]{d} \right\rceil \). Our finding not only contribute to the theoretical understanding of graph coloring but also have potential implications for practical applications. Our next goal is to improve this upper bound by exploring a new method.

ACKNOWLEDGMENT

I would like to express my deepest gratitude for all the editors and reviewers in the review process of IJRSI for their insightful feedback. And special thanks go to my co-author, A.M.C.U.M Athapattu for her invaluable guidance, my friends and family who have been a constant source of encouragement and understanding.

REFERENCES

1. Albertson    O.,   (2004).   Coloring with no 2-Colored P 4’s: The  Electronic Journal of Combinatorics.
2. Erdos and   Lov´asz   L.,   (1975).   Problems and results on 3-chromatic hypergraphs and some related questions: Infinite and finite sets
3. Fertin G, Raspaud   A and Reed   ,   (2004).   Star Coloring of Graphs: Journal of Graph Theory.
4. Graham L and   R¨odl   V.,   (1987).   Numbers in Ramsey     Theory: Surveys in Combinatorics.
5. Gr¨unbaum ,   (1973).   Acyclic Colorings of Planar Graphs: Israel Journal of Mathematics.
6. Harris G and Srinivasan   A.,(2013).   Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing.
7. Hind H, Molloy   M, and Reed   ,   (1997).    Colouring a Graph Frugally: Combinatorica.
8. Mary J.E, Bibi   K.A, and Julietterayan   A.L.M., (2017).    A Study on Star Chromatic Number of Some Special Classes of Graphs: Global Journal of Pure and Applied Mathematics.
9. Spencer    (1977).   Asymptotic Lower Bounds for Ramsey Functions: Discrete Mathematics.
10. Yong H and   Zheng X.D.,   (2010).   A Note on Star Chromatic Number of Graphs: Journal of Mathematical Research & Exposition.