Improved bounds for colouring circle graphs

Davies, James

doi:10.1090/proc/16044

Improved bounds for colouring circle graphs
HTML articles powered by AMS MathViewer

by James Davies PDF

Proc. Amer. Math. Soc. 150 (2022), 5121-5135

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 $2\omega \log _2 (\omega ) +2\omega \log _2(\log _2 (\omega )) + 10\omega$.

References

A. A. Ageev, A triangle-free circle graph with chromatic number $5$, Discrete Math. 152 (1996), no. 1-3, 295–298. MR 1388649, DOI 10.1016/0012-365X(95)00349-2
Dror Bar-Natan, On the Vassiliev knot invariants, Topology 34 (1995), no. 2, 423–472. MR 1318886, DOI 10.1016/0040-9383(95)93237-2
Joan S. Birman and Xiao-Song Lin, Knot polynomials and Vassiliev’s invariants, Invent. Math. 111 (1993), no. 2, 225–270. MR 1198809, DOI 10.1007/BF01231287
André Bouchet, Unimodularity and circle graphs, Discrete Math. 66 (1987), no. 1-2, 203–208. MR 900943, DOI 10.1016/0012-365X(87)90132-4
Sergey Bravyi and Robert Raussendorf, Measurement-based quantum computation with the toric code states, Phys. Rev. A 76 (2007), no. 2, 022304.
Vasilis Capoyleas and János Pach, A Turán-type theorem on chords of a convex polygon, J. Combin. Theory Ser. B 56 (1992), no. 1, 9–15. MR 1182454, DOI 10.1016/0095-8956(92)90003-G
Maria Chudnovsky, Alex Scott, and Paul Seymour, Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings, J. Combin. Theory Ser. B 150 (2021), 195–243. MR 4270097, DOI 10.1016/j.jctb.2021.05.001
James Davies, Vertex-minor-closed classes are $\chi$-bounded, Preprint, arXiv:2008.05069, 2020.
James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak, Grounded $L$-graphs are polynomially $\chi$-bounded, Preprint, arXiv:2108.05611, 2021.
James Davies and Rose McCarty, Circle graphs are quadratically $\chi$-bounded, Bull. Lond. Math. Soc. 53 (2021), no. 3, 673–679. MR 4275079, DOI 10.1112/blms.12447
Vida Dujmović and David R. Wood, On linear layouts of graphs, Discrete Math. Theor. Comput. Sci. 6 (2004), no. 2, 339–357. MR 2081479
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
S. Even and A. Itai, Queues, stacks, and graphs, Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971) Academic Press, New York, 1971, pp. 71–86. MR 0424418
P. Flajolet, J. Françon, and J. Vuillemin, Sequence of operations analysis for dynamic data structures, J. Algorithms 1 (1980), no. 2, 111–141. MR 604861, DOI 10.1016/0196-6774(80)90020-6
Hubert de Fraysseix, A characterization of circle graphs, European J. Combin. 5 (1984), no. 3, 223–238. MR 765628, DOI 10.1016/S0195-6698(84)80005-0
M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou, The complexity of coloring circular arcs and chords, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 216–227. MR 578325, DOI 10.1137/0601025
F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks 3 (1973), 261–273. MR 340106, DOI 10.1002/net.3230030305
Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan, The grid theorem for vertex-minors, J. Combin. Theory, Ser. B (2020), DOI 10.1016/j.jctb.2020.08.004.
Martin Charles Golumbic, Algorithmic graph theory and perfect graphs, 2nd ed., Annals of Discrete Mathematics, vol. 57, Elsevier Science B.V., Amsterdam, 2004. With a foreword by Claude Berge. MR 2063679
A. Gyárfás, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math. 55 (1985), no. 2, 161–166. MR 798532, DOI 10.1016/0012-365X(85)90044-5
A. Gyárfás, Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), 1987, pp. 413–441 (1988). MR 951359
A. Gyárfás and J. Lehel, Covering and coloring problems for relatives of intervals, Discrete Math. 55 (1985), no. 2, 167–180. MR 798533, DOI 10.1016/0012-365X(85)90045-7
Ivo L. Hofacker, Peter Schuster, and Peter F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math. 88 (1998), no. 1-3, 207–237. MR 1658584, DOI 10.1016/S0166-218X(98)00073-0
Alexandr Kostochka and Jan Kratochvíl, Covering and coloring polygon-circle graphs, Discrete Math. 163 (1997), no. 1-3, 299–305. MR 1428585, DOI 10.1016/S0012-365X(96)00344-5
A. V. Kostochka, Upper bounds on the chromatic number of graphs, Trudy Inst. Mat. (Novosibirsk) 10 (1988), no. Modeli i Metody Optim., 204–226, 265 (Russian). MR 945704
Tomasz Krawczyk and Bartosz Walczak, On-line approach to off-line coloring problems on graphs with geometric representations, Combinatorica 37 (2017), no. 6, 1139–1179. MR 3759912, DOI 10.1007/s00493-016-3414-x
Nicolas Marie and Karen Yeats, A chord diagram expansion coming from some Dyson-Schwinger equations, Commun. Number Theory Phys. 7 (2013), no. 2, 251–291. MR 3164865, DOI 10.4310/CNTP.2013.v7.n2.a2
G. V. Nenashev, A bound for the chromatic number of a graph of the intersection of chords on a circle without $K_4$, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 391 (2011), no. Kombinatorika i Teoriya Grafov. III, 149–156, 213 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 184 (2012), no. 5, 629–633. MR 2870246, DOI 10.1007/s10958-012-0886-0
Alexandre Rok and Bartosz Walczak, Coloring curves that cross a fixed curve, Discrete Comput. Geom. 61 (2019), no. 4, 830–851. MR 3943497, DOI 10.1007/s00454-018-0031-z
Alex Scott and Paul Seymour, Induced subgraphs of graphs with large chromatic number. VI. Banana trees, J. Combin. Theory Ser. B 145 (2020), 487–510. MR 4152772, DOI 10.1016/j.jctb.2020.01.004
Alex Scott and Paul Seymour, A survey of $\chi$-boundedness, J. Graph Theory 95 (2020), no. 3, 473–504. MR 4174126, DOI 10.1002/jgt.22601
Naveed A. Sherwani, Algorithms for VLSI physical design automation, Springer Science & Business Media, 2012.
Carsten Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994), no. 1, 180–181. MR 1290638, DOI 10.1006/jctb.1994.1062
Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math. 4 (1952), 2–25 (French). MR 46325, DOI 10.4153/cjm-1952-001-8
Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor, Invariants of the local Clifford group, Phys. Rev. A (3) 71 (2005), no. 2, 022310, 9. MR 2138686, DOI 10.1103/PhysRevA.71.022310