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
Additional Information
- James Davies
- Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
- MR Author ID: 1434420
- Email: jgdavies@uwaterloo.ca
- Received by editor(s): August 13, 2021
- Received by editor(s) in revised form: February 16, 2022
- Published electronically: July 29, 2022
- Communicated by: Isabella Novik
- © Copyright 2022 by the authors
- Journal: Proc. Amer. Math. Soc. 150 (2022), 5121-5135
- MSC (2020): Primary 05C15, 05C62
- DOI: https://doi.org/10.1090/proc/16044