Conflict-Free Colouring of Graphs

DOI10.1017/S0963548313000540zbMath1288.05086arXiv1111.5501OpenAlexW2071386577MaRDI QIDQ5418810

Roman Glebov, Gábor Tardos, Tibor Szabó

Publication date: 28 May 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (17)

Conflict-Free Coloring of Graphs ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ Colorings with neighborhood parity condition ⋮ 1-planar graphs are odd 13-colorable ⋮ On conflict-free proper colourings of graphs without small degree vertices ⋮ Conflict‐free chromatic number versus conflict‐free chromatic index ⋮ A short note on conflict‐free coloring on closed neighborhoods of bounded degree graphs ⋮ A note on the conflict-free chromatic index ⋮ Unique-maximum coloring of plane graphs ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Complexity of conflict-free colorings of graphs ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Conflict-free coloring of string graphs ⋮ Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Unnamed Item ⋮ Remarks on proper conflict-free colorings of graphs

Cites Work

• A lower bound for radio broadcast
• Size and connectivity of the \(k\)-core of a random graph
• Sudden emergence of a giant \(k\)-core in a random graph
• Geometry -- intuitive, discrete, and convex. A tribute to László Fejes Tóth
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks

This page was built for publication: Conflict-Free Colouring of Graphs