Rainbow independent sets on dense graph classes

DOI10.1016/j.dam.2021.04.007zbMath1485.05140arXiv2001.10566OpenAlexW3159303669MaRDI QIDQ831859

Jinha Kim, O-joung Kwon, Min-Ki Kim

Publication date: 24 March 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bounded expansion classbounded neighborhood diversity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items (2)

Keep your distance: land division with separation ⋮ Rainbow Odd Cycles

Cites Work

• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Characterisations and examples of graph classes with bounded expansion
• Colouring graphs with bounded generalized colouring number
• Transversals in row-latin rectangles
• Algorithmic meta-theorems for restrictions of treewidth
• Upper bounds to the clique width of graphs
• Badges and rainbow matchings
• Clustering powers of sparse graphs
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Large rainbow matchings in general graphs
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Rank-width and vertex-minors
• Parameterized Algorithms for Modular-Width
• Map graphs
• First-Order Interpretations of Bounded Expansion Classes
• Erdös--Hajnal Properties for Powers of Sparse Graphs
• On low rank-width colorings
• Complexes of graphs with bounded independence number

This page was built for publication: Rainbow independent sets on dense graph classes