Characterization of forbidden subgraphs for bounded star chromatic number

DOI10.1016/J.DISC.2018.10.012MaRDI QIDQ1712503zbMATH OpenOpenAlexWikidataFDO

Authors Ilkyoo Choi, Ringi Kim, Boram Park

Publication date 22 January 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberacyclic coloringstar coloringforbidden characterization

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The chromatic number of a graph is the minimum $k$ such that the graph has a proper $k$-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are $2$-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. This notion was first suggested by Gr"unbaum in 1973, but no specific name was given. We revive this notion by defining an $H$-avoiding $k$-coloring to be a proper $k$-coloring that forbids a bicolored subgraph $H$. When considering the class $mathcalC$ of graphs with no $F$ as an induced subgraph, it is not hard to see that every graph in $mathcalC$ has bounded chromatic number if and only if $F$ is a complete graph of size at most two. We study this phenomena for the class of graphs with no $F$ as a subgraph for $H$-avoiding coloring. We completely characterize all graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded $H$-avoiding chromatic number for a large class of graphs $H$. As a corollary, our main result implies a characterization of graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded star chromatic number. We also obtain a complete characterization for the acyclic chromatic number.

Recommendations

• Subgraph-avoiding coloring of graphs
• Star chromatic bounds
• Star coloring of certain graph classes
• On forbidden subdivision characterizations of graph classes
• Graph colourings with forbidden \(k\)-coloured subgraphs

Cites work

• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Acyclic colorings of planar graphs
• Graph Theory and Probability
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• Induced subtrees in graphs of large chromatic number
• Radius Three Trees in Graphs with Large Chromatic Number
• Radius two trees specify χ‐bounded classes
• The strong perfect graph theorem

Cited in

(4)

• Subgraph-avoiding coloring of graphs
• Forbidden subgraphs for \(k\) vertex-disjoint stars
• Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture
• Graph clustering via generalized colorings

This page was built for publication: Characterization of forbidden subgraphs for bounded star chromatic number

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