Rainbow induced subgraphs in proper vertex colorings

zbMath1237.05081arXiv1105.3712MaRDI QIDQ3225711

Marek Szykuła, Andrzej P. Kisielewicz

Publication date: 22 March 2012

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

zbMATH Keywords

rainbowinduced subgraphC++vertex coloringreplication graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Vertex colorings without rainbow subgraphs ⋮ On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram \(\mathbb A_n\) ⋮ A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots. ⋮ Applications of matrix morsifications to Coxeter spectral study of loop-free edge-bipartite graphs ⋮ Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete

This page was built for publication: Rainbow induced subgraphs in proper vertex colorings