On variants of conflict-free-coloring for hypergraphs

DOI10.1016/J.DAM.2016.12.018MaRDI QIDQ507574zbMATH OpenOpenAlexFDO

Authors Zhen Cui, Ze-Chun Hu

Publication date 6 February 2017

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

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

zbMATH Keywords

hypergraphconflict-free coloringone dimensional lattice

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: Conflict-free coloring is a kind of vertex coloring of hypergraphs requiring each hyperedge to have a color which appears only on one vertex. More generally, for a positive integer $k$ there are $k$-conflict-free colorings ($k$-CF-colorings for short) and $k$-strong-conflict-free colorings ($k$-SCF-colorings for short). %for some positive integer $k$. Let $H_n$ be the hypergraph of which the vertex-set is $V_n=1,2,dots,n$ and the hyperedge-set $cal{E}_n$ is the set of all (non-empty) subsets of $V_n$ consisting of consecutive elements of $V_n$. Firstly, we study the $k$-SCF-coloring of $H_n$, give the exact $k$-SCF-coloring chromatic number of $H_n$ for $k=2,3$, and present upper and lower bounds of the $k$-SCF-coloring chromatic number of $H_n$ for all $k$. Secondly, we give the exact $k$-CF-coloring chromatic number of $H_n$ for all $k$.

Recommendations

• Conflict-free colourings of uniform hypergraphs with few edges
• Conflict-free coloring and its applications
• On conflict-free multi-coloring
• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• On \(k\)-strong conflict-free multicoloring

Cites work

• scientific article; zbMATH DE number 5506191 (Why is no real title available?)
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• Coloring axis-parallel rectangles
• Coloring geometric range spaces
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Conflict-free coloring made stronger
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of unit disks
• Conflict-free colourings of graphs and hypergraphs
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Deterministic conflict-free coloring for intervals: from offline to online
• On The Chromatic Number of Geometric Hypergraphs
• Online Conflict‐Free Coloring for Intervals
• Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
• Online conflict-free colouring for hypergraphs
• Strong conflict-free coloring for intervals

Cited in

(11)

• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• Conflict-free colourings of uniform hypergraphs with few edges
• Conflict-free coloring and its applications
• Theory and application of conflict resolution with hybrid preference in colored graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
• Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs
• On \(k\)-strong conflict-free multicoloring
• An algebraic formulation of hypergraph colorings
• Essentially disjoint families, conflict free colorings and Shelah's revised GCH
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

This page was built for publication: On variants of conflict-free-coloring for hypergraphs

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