Covering and coloring problems for relatives of intervals

DOI10.1016/0012-365X(85)90045-7zbMath0569.05020OpenAlexW2051822734WikidataQ56503306 ScholiaQ56503306MaRDI QIDQ1061132

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0012-365x(85)90045-7

zbMATH Keywords

stability number chromatic number clique number overlap graphs multiple boxes multiple intervals arcs of a circle chords of a circle clique-cover number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of packing and covering (05B40)

Related Items (48)

Packing and covering with balls on Busemann surfaces ⋮ Some geometric applications of Dilworth's theorem ⋮ Disjointness graphs of segments in the space ⋮ Improved bounds for colouring circle graphs ⋮ Colouring relatives of intervals on the plane. II: Intervals and rays in two directions ⋮ Coloring interval graphs with First-Fit ⋮ Quasi-planar graphs have a linear number of edges ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ A triangle-free circle graph with chromatic number 5 ⋮ On the unit interval number of a graph ⋮ On bounding the chromatic number of L-graphs ⋮ Triangle-free geometric intersection graphs with large chromatic number ⋮ On point covers of multiple intervals and axis-parallel rectangles ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Edge-covers in $d$-interval hypergraphs ⋮ Triangle-free intersection graphs of line segments with large chromatic number ⋮ From a $(p, 2)$-theorem to a tight $(p, q)$-theorem ⋮ Coloring $K_{k}$-free intersection graphs of geometric objects in the plane ⋮ Approximate symmetries of Hamiltonians ⋮ Disjointness graphs of short polygonal chains ⋮ Coloring triangle-free L-graphs with $O (\log \log n)$ colors ⋮ Lower bounds for piercing and coloring boxes ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ Using Brouwer’s Fixed Point Theorem ⋮ Piercing translates and homothets of a convex body ⋮ On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes ⋮ Coloring intersection graphs of $x$-monotone curves in the plane ⋮ On point covers of parallel rectangles ⋮ Coloring the complements of intersection graphs of geometric figures ⋮ Intersection of parallelepipeds in $\mathbb R^d$ ⋮ Fractional covers and matchings in families of weighted $d$-intervals ⋮ Piercing axis-parallel boxes ⋮ Covering boxes by points ⋮ Some properties of $k$-Delaunay and $k$-Gabriel graphs ⋮ A Turán-type theorem on chords of a convex polygon ⋮ Coloring translates and homothets of a convex body ⋮ On Wegner's inequality for axis-parallel rectangles ⋮ From a $(p,2)$-Theorem to a Tight $(p,q)$-Theorem ⋮ Gallai-type results for multiple boxes and forests ⋮ Coloring non-crossing strings ⋮ Transversal numbers of translates of a convex body ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems ⋮ Every circle graph of girth at least 5 is 3-colourable ⋮ Coloring a set of touching strings ⋮ Piercing numbers in approval voting ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ Interval graphs and related topics

Cites Work

This page was built for publication: Covering and coloring problems for relatives of intervals