Covering and coloring polygon-circle graphs
From MaRDI portal
Publication:1356563
DOI10.1016/S0012-365X(96)00344-5zbMath0871.05025WikidataQ56503310 ScholiaQ56503310MaRDI QIDQ1356563
Jan Kratochvíl, Alexandr V. Kostochka
Publication date: 24 September 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
chromatic numberintersection graphspolygonsclique covering numberoverlap graphscircle graphsindependence numbersbinding functionspolygon-circle graphs
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items
Disjointness graphs of segments in the space ⋮ Improved bounds for colouring circle graphs ⋮ On the structure of certain intersection graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ On the chromatic number of some geometric type Kneser graphs ⋮ Blocking visibility for points in general position ⋮ A triangle-free circle graph with chromatic number 5 ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ On Strict (Outer-)Confluent Graphs ⋮ Triangle-free geometric intersection graphs with large chromatic number ⋮ Coloring curves that cross a fixed curve ⋮ An upper bound on the chromatic number of a circle graph without \(K_4\) ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Coloring circle graphs ⋮ Classes of graphs with small rank decompositions are \(\chi \)-bounded ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Edge colorings avoiding patterns ⋮ Algorithms for induced biclique optimization problems ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Maximum independent set and maximum clique algorithms for overlap graphs ⋮ Independent sets and chromatic numbers of circle graphs ⋮ 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 ⋮ Induced matchings in intersection graphs. ⋮ Coloring intersection graphs of \(x\)-monotone curves in the plane ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ On circle graphs with girth at least five ⋮ On the page number of RNA secondary structures with pseudoknots ⋮ Islands in Graphs on Surfaces ⋮ Finding common structured patterns in linear graphs ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ Coloring non-crossing strings ⋮ On fixed-order book thickness parameterized by the pathwidth of the vertex ordering ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ On the chromatic number of disjointness graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Coloring a set of touching strings ⋮ Circle graphs are quadratically χ‐bounded ⋮ Hasse diagrams with large chromatic number ⋮ Independent packings in structured graphs ⋮ Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
Cites Work
