On the chromatic number of multiple interval graphs and overlap graphs
From MaRDI portal
Publication:1061131
DOI10.1016/0012-365X(85)90044-5zbMath0569.05019WikidataQ56503305 ScholiaQ56503305MaRDI QIDQ1061131
Publication date: 1985
Published in: Discrete Mathematics (Search for Journal in Brave)
chromatic numberclique numbercircular-arc graphsNP-complete problemoverlap graphsmultiple interval graphs
Related Items
Disjointness graphs of segments in the space ⋮ Improved bounds for colouring circle graphs ⋮ Covering and coloring polygon-circle graphs ⋮ Quasi-planar graphs have a linear number of edges ⋮ 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 ⋮ Coloring curves that cross a fixed curve ⋮ Coloring polygon visibility graphs and their generalizations ⋮ A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Coloring circle graphs ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Ramsey properties of semilinear graphs ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes ⋮ Coloring intersection graphs of arc-connected sets in the plane ⋮ Coloring intersection graphs of \(x\)-monotone curves in the plane ⋮ A note on fractional coloring and the integrality gap of LP for maximum weight independent set ⋮ Fractional covers and matchings in families of weighted \(d\)-intervals ⋮ A Turán-type theorem on chords of a convex polygon ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Coloring translates and homothets of a convex body ⋮ Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ Chi-boundedness of graph classes excluding wheel vertex-minors ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ On fixed-order book thickness parameterized by the pathwidth of the vertex ordering ⋮ On the chromatic number of disjointness graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Quasi-planar Graphs ⋮ Circle graphs are quadratically χ‐bounded ⋮ Hasse diagrams with large chromatic number ⋮ Interval graphs and related topics ⋮ Covering and coloring problems for relatives of intervals ⋮ Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
Cites Work
