Precoloring extension in planar near-Eulerian-triangulations
EUROCOMB’23
393–400
Kennth Appel and Wolfgang Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429-490, 1977.
https://doi.org/10.1215/ijm/1256049011
Zdenek Dvorak, Daniel Kral' and Robin Thomas. Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations. ArXiv, 1509.01013, September 2015.
Zdenek Dvorak, Daniel Kral', and Robin Thomas. Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory, Series B, 145:376-432, 2020.
https://doi.org/10.1016/j.jctb.2020.06.005
Zdenek Dvorak, Daniel Kral', and Robin Thomas. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of combinatorial Theory, Series B, 150:270-304, 2021.
https://doi.org/10.1016/j.jctb.2020.09.001
Zdenek Dvorak, Daniel Kral', and Robin Thomas. Three-coloring triangle-free graphs on surfaces VII. A linear time algorithm. Journal of Combinatorial Theory, Series B, 152:483-504, 2022.
https://doi.org/10.1016/j.jctb.2021.07.002
David Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '95, page 632-640, USA, 1995. Society for Industrial and Applied Mathematics.
Steve Fisk. Geometric coloring theory. Advances in Mathematics, 24(3):298-340, 1977
https://doi.org/10.1016/0001-8708(77)90061-5
Steve Fisk. The nonexistence of colorings. Journal of Combinatorial Theory, Series B. 24:247-248,1978.
https://doi.org/10.1016/0095-8956(78)90028-X
Pavol Hell. Absolute retracts in graphs. In Ruth A Bari and Frank Harary, editors, Graphs and Combinatorics, pages 291-301, Berlin, Heidelberg, 1974. Springer Berlin Heidelberg.
https://doi.org/10.1007/BFb0066450
Joan Hutchinson. Three-coloring graphs embedded on surfaces with all faces even-sided. Journal of Combinatorial Theory Series B, 65:139-155, 1995.
https://doi.org/10.1006/jctb.1995.1047
Joan Hutchinson, Bruce Richter, and Paul D. Seymour. Colouring Eulerian triangulations. Journal of Combinatorial Theory Series B, 84:225-239, 2002.
https://doi.org/10.1006/jctb.2001.2074
Bojan Mohar. Coloring Eulerian triangulations of the projective plane. Discrete mathematics, 244:339-343, 2002.
https://doi.org/10.1016/S0012-365X(01)00092-9
Bojan Mohar and Paul D. Seymour. Coloring locally bipartite graphs on surfaces. Journal of Combinatorial Theory Series B, 84:301-310, 2002.
https://doi.org/10.1006/jctb.2001.2086
Atsuhiro Nakamoto. 5-chromatic even triangulations on surfaces. Discrete Mathematics, 308(12):2571-2580, 2008.
https://doi.org/10.1016/j.disc.2007.05.028
Atsuhiro Nakamoto, Seiya Negami, and Katsurhiro Ota. Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces. Discrete Mathematics, 285:211-218, 2004.
https://doi.org/10.1016/j.disc.2004.04.008
Luke Postle and Robin Thomas. Hyperbolic familes and coloring graphs on surfaces. Transactions of the American Mathematical Society, Series B. Volume 5, Pages 167-221.
https://doi.org/10.1090/btran/26
Neil Robertson and Paul D. Seymour. Graph minors VI. Disjoint paths across a disc. Journal of Combinatorial Theory, Series B, 41:115-138,1986.
https://doi.org/10.1016/0095-8956(86)90031-6
Neil Roberston and Paul D Seymour. Graph minors VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B, 45:212-254, 1988.
https://doi.org/10.1016/0095-8956(88)90070-6
Larry Stockmeyer. Planar 3-colorability is polynomial complete. SIGACT news, 5(3):19-25 jul 1973.
https://doi.org/10.1145/1008293.1008294
Carsten Thomassen. Five-coloring graphs on surfaces. Journal of Combinatorial Theory Series B, 59:89-105, 1993.
https://doi.org/10.1006/jctb.1993.1057
Carsten Thomassen. Color-critical graphs on a fixed surface. Journal of Combinatorial Theory, Series B, 70(1):67-100,1997.
https://doi.org/10.1006/jctb.1996.1722
Carsten Thomassen. The chromatic number of a graph of girth 5 on a fixed surface. Journal of Combinatorial Theory, Series B, 87:38-71, 2003.
https://doi.org/10.1016/S0095-8956(02)00027-8
William Tutte. A contribution to the theory of chromatic polynomials. Canadian Journal of Mathematics, 6:80-91, 1954.
https://doi.org/10.4153/CJM-1954-010-9
Daniel Youngs. 4-chromatic projective graphs. Journal of Graph Theory, 21:219-227, 1996
https://doi.org/10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová, Robert Šámal