Circle graphs are quadratically $\chi$-bounded

Abstract

We prove that the chromatic number of a circle graph with clique number $\omega$ is at most $7{\omega }^2$.

arXiv comment7 pages

References in corpus (4)

• On-line approach to off-line coloring problems on graphs with geometric representations
• Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
• Graphs of bounded cliquewidth are polynomially $\chi$-bounded
• A survey of $\chi$-boundedness

Cited by in corpus (6)

• Book Embeddings of Graph Products
• Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness
• Grounded L-graphs are polynomially $\chi$-bounded
• Isometric path complexity of graphs
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• New Formulation for Coloring Circle Graphs and its Application to Capacitated Stowage Stack Minimization