Precoloring extension in planar near-Eulerian-triangulations

EUROCOMB’23

Abstract
We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors.

Pages:
393–400
References

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

Metrics

0

Views

0

PDF views