Covering and coloring polygon-circle graphs
From MaRDI portal
Publication:1356563
DOI10.1016/S0012-365X(96)00344-5zbMATH Open0871.05025WikidataQ56503310 ScholiaQ56503310MaRDI QIDQ1356563FDOQ1356563
Authors: Jan Kratochvíl, Alexandr Kostochka 
Publication date: 24 September 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
Recommendations
chromatic numberintersection graphspolygonsclique covering numberoverlap graphscircle graphsindependence numbersbinding functionspolygon-circle graphs
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Circle graph obstructions
- Thresholds for classes of intersection graphs
- Reducing prime graphs and recognizing circle graphs
- On the chromatic number of multiple interval graphs and overlap graphs
- Corrigendum
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (56)
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- On families of planar DAGs with constant stack number
- Edge colorings avoiding patterns
- Edge colorings avoiding patterns
- Treewidth, Circle Graphs, and Circular Drawings
- Treewidth, circle graphs and circular drawings
- The graphs with maximum induced matching and maximum matching the same size
- On the page number of upward planar directed acyclic graphs
- Triangle-free geometric intersection graphs with large chromatic number
- Title not available (Why is that?)
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Coloring intersection graphs of arc-connected sets in the plane
- Independent packings in structured graphs
- On strict (outer-)confluent graphs
- Finding common structured patterns in linear graphs
- On the structure of certain intersection graphs
- Circle graphs are quadratically χ‐bounded
- Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
- Blocking visibility for points in general position
- Approximation algorithms for maximum weight k-coverings of graphs by packings
- On-line approach to off-line coloring problems on graphs with geometric representations
- Conflict-free coloring of string graphs
- Islands in Graphs on Surfaces
- On circle graphs with girth at least five
- Coloring non-crossing strings
- Maximum independent set and maximum clique algorithms for overlap graphs
- Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Hasse diagrams with large chromatic number
- Coloring curves that cross a fixed curve
- Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
- On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
- Title not available (Why is that?)
- On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
- Coloring clean and \(K_4\)-free circle graphs
- Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
- A triangle-free circle graph with chromatic number 5
- An upper bound on the chromatic number of a circle graph without \(K_4\)
- Independent sets and chromatic numbers of circle graphs
- Improved bounds for colouring circle graphs
- On the chromatic number of disjointness graphs of curves
- Disjointness graphs of segments in the space
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
- Algorithms for induced biclique optimization problems
- On the chromatic number of some geometric type Kneser graphs
- On the page number of RNA secondary structures with pseudoknots
- Outerstring graphs are \(\chi \)-bounded
- Coloring a set of touching strings
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Induced matchings in intersection graphs.
- Coloring circle graphs
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Coloring Hasse diagrams and disjointness graphs of curves
- Finding a maximum induced matching in weakly chordal graphs
This page was built for publication: Covering and coloring polygon-circle graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356563)
