Improved bounds for colouring circle graphs

DOI10.1090/proc/16044zbMath1498.05093arXiv2107.03585OpenAlexW4220969056MaRDI QIDQ5039236

James E. Davies

Publication date: 12 October 2022

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

chromatic number\(\chi\)-bounding function for circle graphs

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line approach to off-line coloring problems on graphs with geometric representations
• A characterization of circle graphs
• On the chromatic number of multiple interval graphs and overlap graphs
• Covering and coloring problems for relatives of intervals
• Unimodularity and circle graphs
• A Turán-type theorem on chords of a convex polygon
• Combinatorics of RNA secondary structures
• Every planar graph is 5-choosable
• Covering and coloring polygon-circle graphs
• On the Vassiliev knot invariants
• Algorithmic graph theory and perfect graphs
• A triangle-free circle graph with chromatic number 5
• An upper bound on the chromatic number of a circle graph without \(K_4\)
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• The grid theorem for vertex-minors
• Induced subgraphs of graphs with large chromatic number. VI. Banana trees
• Knot polynomials and Vassiliev's invariants
• Coloring curves that cross a fixed curve
• A chord diagram expansion coming from some Dyson-Schwinger equations
• Invariants of the local Clifford group
• Sequence of operations analysis for dynamic data structures
• The Complexity of Coloring Circular Arcs and Chords
• Circle graphs are quadratically χ‐bounded
• A survey of χ‐boundedness
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Sur Un Problème De Configurations Et Sur Les Fractions Continues

This page was built for publication: Improved bounds for colouring circle graphs