Bounds on vertex colorings with restrictions on the union of color classes

DOI10.1002/JGT.20501MaRDI QIDQ3083409zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, C. R. Subramanian

Publication date 21 March 2011

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

Full work available at URL https://doi.org/10.1002/jgt.20501

zbMATH Keywords

vertex coloringforbidden subgraphsproper coloringacyclic coloringsbounded tree width

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Bounds on edge colorings with restrictions on the union of color classes
• Bounded vertex colorings of graphs
• Vertex coloring without large polychromatic stars
• Coloring subgraphs with restricted amounts of hues
• scientific article; zbMATH DE number 446487

Cites work

• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Bounds on edge colorings with restrictions on the union of color classes
• Colouring a graph frugally
• Colouring graphs with bounded generalized colouring number
• Discrete Mathematics
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Forbidden subgraph colorings and the oriented chromatic number
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• Radiocoloring in planar graphs: Complexity and approximations
• Star coloring of graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(6)

• Intersection dimension and graph invariants
• Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings
• Star coloring of graphs with girth at least five
• Bounds on edge colorings with restrictions on the union of color classes
• Improved bounds for centered colorings
• Cooperative coloring of some graph families

This page was built for publication: Bounds on vertex colorings with restrictions on the union of color classes

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