On star 5-colorings of sparse graphs

DOI10.1016/J.DAM.2021.02.009zbMATH Open1459.05076arXiv1903.10133OpenAlexW3132853216MaRDI QIDQ2656970FDOQ2656970

Authors: Ilkyoo Choi, Boram Park 

Publication date: 17 March 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A extit{star $k$-coloring} of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$, its extit{star chromatic number}, denoted $ch{i}_s(G)$, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree of a graph; the extit{maximum average degree}, denoted $mad(G)$, of a graph $G$ is $maxleftfrac2|E(H)||V(H)|:HsubsetGight$. It is known that for a graph $G$, if $mad(G)<frac83$, then $ch{i}_s(G)leq6$, and if $mad(G)<frac187$ and its girth is at least 6, then $ch{i}_s(G)le5$. We improve both results by showing that for a graph $G$, if $mad(G)lefrac83$, then $ch{i}_s(G)le5$. As an immediate corollary, we obtain that a planar graph with girth at least 8 has a star 5-coloring, improving the best known girth condition for a planar graph to have a star 5-coloring.

Full work available at URL: https://arxiv.org/abs/1903.10133

Recommendations

• Star coloring of sparse graphs
• Star edge coloring of graphs with \(\mathrm{Mad}(G)<\frac{14}{5}\)
• Star coloring high girth planar graphs
• 8-star-choosability of a graph with maximum average degree less than 3
• Star coloring planar graphs from small lists

zbMATH Keywords

star coloringmaximum average degreesparse graphstar 5-coloring

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Cites Work

• Note to the paper of Grünbaum on acyclic colorings
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• On acyclic colorings of planar graphs
• Colorings of plane graphs: a survey
• Acyclic colorings of planar graphs
• Coloring with no 2-colored \(P_4\)'s
• Star coloring of graphs
• Star coloring high girth planar graphs
• I,F-partitions of sparse graphs
• Star coloring planar graphs from small lists
• Star coloring bipartite planar graphs
• Star coloring of sparse graphs
• Star Chromatic Index
• 6-Star-Coloring of Subcubic Graphs
• An introduction to the discharging method via graph coloring
• 8-star-choosability of a graph with maximum average degree less than 3
• On a star chromatic index of subcubic graphs
• List star edge coloring of sparse graphs
• Star list chromatic number of planar subcubic graphs
• Star chromatic index of subcubic multigraphs

Cited In (7)

• Star coloring of sparse graphs
• 8-star-choosability of a graph with maximum average degree less than 3
• I,F-partitions of sparse graphs
• Star coloring high girth planar graphs
• Circular \((5,2)\)-coloring of sparse graphs
• Star coloring of graphs with girth at least five
• Oriented 5-coloring of sparse plane graphs

This page was built for publication: On star 5-colorings of sparse graphs

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