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

DOI10.1002/jgt.20501zbMath1228.05147MaRDI QIDQ3083409

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 coloring; forbidden subgraphs; proper coloring; acyclic colorings; bounded tree width

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings, Star coloring of graphs with girth at least five, Intersection dimension and graph invariants

Cites Work

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