On variants of conflict-free-coloring for hypergraphs

DOI10.1016/J.DAM.2016.12.018zbMATH Open1355.05106arXiv1107.0138OpenAlexW2963994043MaRDI QIDQ507574FDOQ507574

Authors: Zhen Cui, Ze-Chun Hu 

Publication date: 6 February 2017

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

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$.

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

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

zbMATH Keywords

hypergraphconflict-free coloringone dimensional lattice

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)