Improved bounds for colouring circle graphs

DOI10.1090/PROC/16044MaRDI QIDQ5039236zbMATH OpenOpenAlexFDO

Authors 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

\(\chi\)-bounding function for circle graphschromatic number

Mathematics Subject Classification ID

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

Abstract: We prove the first $chi$-bounding function for circle graphs that is optimal up to a constant factor. To be more precise, we prove that every circle graph with clique number at most $omega$ has chromatic number at most $2omegalo{g}_2(omega)+2omegalo{g}_2(lo{g}_2(omega))+10omega$.

Recommendations

• Coloring circle graphs
• Coloring clean and \(K_4\)-free circle graphs
• The complexity of colouring circle graphs (extended abstract)
• scientific article; zbMATH DE number 1534394
• A triangle-free circle graph with chromatic number 5

Cites work

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

Cited in

(25)

• Covering and coloring polygon-circle graphs
• Coloring clean and \(K_4\)-free circle graphs
• Coloring circle graphs
• scientific article; zbMATH DE number 4108789 (Why is no real title available?)
• scientific article; zbMATH DE number 1534394 (Why is no real title available?)
• The complexity of colouring circle graphs (extended abstract)
• 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
• Vertex-minors of graphs: a survey
• On families of planar DAGs with constant stack number
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Treewidth, circle graphs and circular drawings
• Directed acyclic outerplanar graphs have constant stack number
• Reuniting -boundedness with polynomial -boundedness
• New formulation for coloring circle graphs
• A survey of degree-boundedness
• Pivot-minors and the Erdős-Hajnal conjecture
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Forbidden patterns in mixed linear layouts
• Sublinear hitting sets for some geometric graphs
• The page number of monotone directed acyclic outerplanar graphs is four or five
• Independent sets and chromatic numbers of circle graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5039236)