Star coloring of sparse graphs

DOI10.1002/JGT.20392MaRDI QIDQ3652552zbMATH OpenOpenAlexFDO

Authors Yuehua Bu, Daniel W. Cranston, Mickaël Montassier, André Raspaud, Weifan Wang

Publication date 18 December 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

sparse graphsstar coloringstar forests

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: A proper coloring of the vertices of a graph is called a emph{star coloring} if the union of every two color classes induces a star forest. The star chromatic number $ch{i}_s(G)$ is the smallest number of colors required to obtain a star coloring of $G$. In this paper, we study the relationship between the star chromatic number $ch{i}_s(G)$ and the maximum average degree $mboxMad(G)$ of a graph $G$. We prove that: (1) If $G$ is a graph with $mboxMad(G)<frac2611$, then $ch{i}_s(G)leq4$. (2) If $G$ is a graph with $mboxMad(G)<frac187$ and girth at least 6, then $ch{i}_s(G)leq5$. (3) If $G$ is a graph with $mboxMad(G)<frac83$ and girth at least 6, then $ch{i}_s(G)leq6$. These results are obtained by proving that such graphs admit a particular decomposition into a forest and some independent sets.

Recommendations

• On star 5-colorings of sparse graphs
• Star edge coloring of graphs with \(\mathrm{Mad}(G)<\frac{14}{5}\)
• Star coloring high girth planar graphs
• Star coloring of graphs
• Star coloring of subcubic graphs

Cites work

• Acyclic colorings of planar graphs
• Coloring with no 2-colored \(P_4\)'s
• Star coloring high girth planar graphs
• Star coloring of graphs

Cited in

(26)

• Star coloring high girth planar graphs
• Star 5-edge-colorings of subcubic multigraphs
• Star coloring of certain graph classes
• On the number of 2-packings in a connected graph
• An upper bound for the choice number of star edge coloring of graphs
• Star list chromatic number of planar subcubic graphs
• Representing graphs as the intersection of cographs and threshold graphs
• Additive list coloring of planar graphs with given girth
• On the star chromatic index of generalized Petersen graphs
• On star 5-colorings of sparse graphs
• Weak unit disk and interval representation of graphs
• I,F-partitions of sparse graphs
• Star edge coloring of corona product of path and wheel graph families
• Star edge coloring of some classes of graphs
• Star coloring planar graphs from small lists
• Star coloring of cubic graphs
• 6-Star-Coloring of Subcubic Graphs
• An introduction to the discharging method via graph coloring
• Star edge coloring of graphs with \(\mathrm{Mad}(G)<\frac{14}{5}\)
• 8-star-choosability of a graph with maximum average degree less than 3
• Block colourings of star systems
• Injective edge-coloring of subcubic graphs
• Degenerate and star colorings of graphs on surfaces
• Star colouring and locally constrained graph homomorphisms
• Strong arboricity of graphs
• Additive coloring of planar graphs

This page was built for publication: Star coloring of sparse graphs

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