On the cyclic coloring conjecture

Roman Sotak; Stanislav Jendrol

REVIEW

On the cyclic coloring conjecture

Stanislav Jendrol, Roman Sotak

Combinatorics · Submitted 22 Sep 2020 · 28 references

Pith's verdict: A genuinely useful reduction of Borodin's cyclic coloring conjecture, but the proof of the reduction needs a real fix around 2-connectedness before I'd trust the equivalence.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 27, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2009.10436 (version 1)

Pith IDASTJ3CZU, Pith's permanent record of this paper and its review

CitationRoman Sotak, Stanislav Jendrol. "On the cyclic coloring conjecture." arXiv:2009.10436 (2020). https://pith.science/paper/ASTJ3CZU

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

First thing to know: the reduction in Theorem 4 is the real contribution. I don't think anyone had observed that the full conjecture is equivalent to the subdivision-restricted version, and the proof strategy—minimal counterexample, separate along a short separating cycle, glue—is the right instinct. The later bounds (Theorems 5–8 and the corollaries) are mostly tidy applications of known results, and the tight examples are explicit. No circularity, no fitted parameters; the citation pattern is fine.

Now the soft spot. The sentence "It is easy to see that H is 2-connected" in the proof of Theorem 4 is doing heavy lifting. The stress-test concern is legitimate: if H had a cut vertex, Theorem 3 doesn't supply a separating cycle, and gluing colorings of the two sides is not automatic—you have to permute colors around the cut vertex so that faces passing through it stay rainbow. The paper neither proves nor cites a lemma for that. I don't think the claim is false; it's probably true and known to the authors. But it's not a one-liner, and a referee should push for the argument.

Theorem 3 has similar "easy to see" bits in the four-faces and 2-face cases, but those are more routine and less concerning. Corollary 5's proof mentions a lower bound on Delta* without deriving it; it's true (since Delta*(G) ≥ 3(k+1) ≥ 2+8/(k+1)), so that's a minor presentational slip, not a mathematical error. My read of the rest: the gluing along the separating cycle in Theorem 4 is sound once 2-connectedness is granted, and the applications in Section 6 check out.

Bottom line: if I worked in plane graph coloring, I'd want this result in the literature, and I'd cite it. But I'd want the 2-connectedness gap closed first. That's a fixable problem, not a fatal one. Send it to a serious referee.

Referee report

Significance

If Theorem 4 is correct, it is a valuable structural reduction: a strong 1984 conjecture for all connected plane graphs is reduced to a restricted family for which substantially better tools exist. Theorems 5–8 give concrete, sometimes tight bounds, and the corollaries cover several wide families. The paper's arguments are explicit where they are given, and the use of external results (Four Color Theorem, Shannon, Vizing–Gupta, prior cyclic coloring bounds) is transparent; there is no parameter fitting. However, the central equivalence is currently not established because the 2-connectedness of the minimal counterexample is asserted without proof, and Theorem 3's four-face/2-face cases are left as 'easy to see'. The secondary results are interesting but their proofs also contain a gap in Corollary 5.

Major objections (3)

[Section 5, Theorem 4] The proof asserts 'It is easy to see that H is 2-connected' without argument. This is load-bearing: Theorem 3, which supplies the separating cycle C_n used for the induction, is stated only for 2-connected plane graphs. If a minimal counterexample had a cut vertex, the proof gives no separating cycle and no induction step. The missing statement is not routine: in a plane graph with a cut vertex a single face can contain vertices from different blocks (for example, two triangles sharing a vertex have an outer face containing all vertices of both blocks), so independent cyclic colorings of the blocks do not automatically yield a cyclic coloring of the whole graph, and minimality by number of faces does not obviously rule this out because the face constraints on the pieces are weaker than on the whole. A lemma proving 2-connectedness of a minimal counterexample, or a gluing argument around cut vertices, is needed for the equivalence of Conjectures 1 and 3.
[Section 3, Theorem 3] The proof begins 'It is easy to see that the theorem holds if G has exactly four faces or it contains a 2-face'. Since Theorem 3 is the structural statement that powers the reduction in Theorem 4, this case needs an actual proof; as written it is not verifiable from the text. In particular, for the four-face case one must show explicitly that a 2-connected plane graph with four faces that is not a subdivision of a simple 3-connected plane graph contains a separating cycle of length at most Δ*(G).
[Section 7, Corollary 5] The proof of Corollary 5 contains an invalid inequality. It derives χc(G) ≤ Δ*(R)(k+1)+k+5 ≤ floor(3/2 Δ*(R)(k+1)) from the hypothesis Δ*(G) ≥ 2 + 8/(k+1). For a regular subdivision with k=1 and Δ*(R)=3, the left side is 12 and the right side is 9, so the displayed inequality is false; moreover the hypothesis is automatically satisfied for all admissible G (since Δ*(G) ≥ 3(k+1) ≥ 2+8/(k+1) for k≥1) and thus cannot justify the bound. The proof needs a case analysis using the actual value of r in Theorem 2 (r=1 for Δ*(R)=3, r=2 for Δ*(R)=4, etc.), or a corrected threshold on Δ*(R), with the floor handled explicitly.

Minor objections (5)

[Section 5, Theorem 4] The gluing step after cutting along C_n should state explicitly that the colorings of H_1 and H_2 can be permuted so that the colors on the shared cycle C_n agree; as written, 'we can combine' is terse.
[Section 6, Theorem 7] The statement says 'subdivision of a 3-connected plane graph R', but the proof and Theorem 2 require simple 3-connected plane graphs; please make 'simple' explicit to avoid ambiguity about 2-faces and multiple edges.
[Section 2, reduction properties] The structural observation about the reduction R(G) (the three bullets) is used in Theorem 3 but is not stated as a formal lemma; expanding it would improve verifiability of Theorem 3.
[Section 4, Lemma 2] The graph D_3 is called a triangular prism but the notation D_3 is not defined; please define it.
[Section 7, Corollary 5] The displayed hypothesis 'Δ*(G) ≥ 2 + 8/(k+1)' appears to be a typo for a condition on Δ*(R); in any case it is not sufficient, as explained in the major comment.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper proves that the 1984 Cyclic Coloring Conjecture for all connected plane graphs is equivalent to the same bound restricted to subdivisions of simple 3-connected plane graphs, so settling the small family settles the old conjecture.

The reading

This note attacks the 1984 Cyclic Coloring Conjecture, which states that every connected plane graph $G$ admits a vertex coloring in which any two vertices sharing a face receive different colors, using at most $\lfloor \frac{3}{2}\Delta^*(G)\rfloor$ colors, where $\Delta^*(G)$ is the largest face size. The authors prove a reduction: the full conjecture holds if and only if the same bound holds for the much smaller family of subdivisions of simple 3-connected plane graphs (Theorem 4). The proof takes a hypothetical minimal counterexample, cuts it along a separating cycle of length at most $\Delta^*(G)$, colors the two smaller pieces, and glues the colorings back together. On the restricted family the paper proves four new upper bounds, three of them tight, and derives the conjecture for subdivisions of triangulations, quadrangulations, even-face pentagulations, and regular subdivisions. If the reduction is sound, the old open problem has been compressed to a bounded subproblem that appears substantially closer to reach.

What carries the argument

The load-bearing mechanism is the separating-cycle reduction of Theorem 3: every 2-connected plane graph with at least four faces that is not a subdivision of a simple 3-connected plane graph contains a separating cycle $C_n$ of length $n \leq \Delta^*(G)$. The reduction $R(G)$, obtained by contracting each maximal path whose interior vertices all have degree 2 into a single edge, organizes the argument: if $R(G)$ is simple and 3-connected the graph is already in the good family, otherwise $R(G)$ carries a 2-face or a suitable 2-vertex cut, which is converted into the short separating cycle. The second mechanism is the gluing step in Theorem 4: two cyclic colorings of the pieces of a graph cut along a cycle of length at most $\Delta^*$ can be aligned on the shared cycle, because every face of the whole graph survives in one of the pieces and the pieces meet only along the cycle. For the bounds on the restricted family, the central object is the subdivision multigraph $S(G)$, whose vertices are the faces of $G$ and whose edges are the degree-2 vertices of $G$, each edge joining the two faces its vertex is incident with; coloring the inserted vertices is exactly edge-coloring $S$, so a classical edge-coloring bound and an edge-coloring bound with a multiplicity term supply the color counts in Theorems 7 and 8.

Extended reading notes

Core claim

The central claim is Theorem 4: the Cyclic Coloring Conjecture (Conjecture 1, $\chi_c(G) \leq \lfloor \frac{3}{2}\Delta^*(G)\rfloor$ for every connected plane graph $G$) is equivalent to Conjecture 3, the same bound restricted to subdivisions of simple 3-connected plane graphs. One direction is immediate; the paper proves the converse. A counterexample $H$ with the fewest faces, then fewest vertices, is asserted to be 2-connected, is shown by Lemma 1 to have at least four faces, and cannot be a subdivision of a simple 3-connected plane graph; Theorem 3 then provides a separating cycle $C_n$ with $n \leq \Delta^*(H)$. Cutting $H$ along $C_n$ gives two smaller plane graphs $H_1, H_2$ with maximum face degree at most $\Delta^*(H)$; applying the conjectured bound to each and adjusting the palettes so the two colorings agree on the $n$ vertices of $C_n$ yields a cyclic coloring of $H$ with at most $\lfloor \frac{3}{2}\Delta^*(H)\rfloor$ colors, a contradiction. For the restricted family, the paper proves four new bounds: one (Theorem 5) by specializing a known $k^*$-based bound, using $k^* = t(G) + 2$ for subdivisions, and three (Theorems 6, 7, 8) by transferring the problem of coloring inserted degree-2 vertices to an edge-coloring problem on an auxiliary multigraph; three of the four bounds are shown to be tight.

Load-bearing premise

The proof assumes, without giving an argument, that a counterexample with the fewest possible faces and then the fewest possible vertices must be 2-connected, and the separating-cycle theorem it relies on applies only to 2-connected graphs; if a minimal counterexample could have a cut vertex, the reduction and the claimed equivalence would not follow from the proof as written.

Editorial extensions

If this is right

The 1984 conjecture is true exactly if its bound holds for subdivisions of simple 3-connected plane graphs, so work on it can ignore all other connected plane graphs (Theorem 4).
The conjecture is verified for subdivisions of plane triangulations, of simple 3-connected plane quadrangulations, and of simple 3-connected plane pentagulations with even maximum face degree (Corollary 2).
The conjecture is verified for regular subdivisions of simple 3-connected plane graphs whose edges are all replaced by paths of one common length at least two, and for subdivisions whose maximum face degree is large enough compared with $t(G)$, the length of the longest path consisting of degree-2 vertices (Corollaries 1, 3, and 5).
Three of the four new bounds on the restricted family are tight, and a prism construction (Lemma 2) attains $\lfloor \frac{3}{2}\Delta^*(G)\rfloor$ exactly, so the restricted family already contains graphs that meet the conjectured ceiling.
The paper's Conjecture 4, that $\chi_c(G) \leq \Delta^*(G) + t(G) + 2$ for such subdivisions, unifies two older conjectures and cannot be improved, since the same prism construction is tight for it.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The gluing step needs only that the separating cycle is no longer than the color budget, so the equivalence would survive a relaxation of Theorem 3 to separating cycles of length up to $\lfloor \frac{3}{2}\Delta^*\rfloor$; the paper proves the stronger length bound $n \leq \Delta^*$ but does not use the extra room.
Since inserted degree-2 vertices are colored through the subdivision multigraph, the conjecture is, for this family, an edge-coloring problem in disguise; better edge-coloring bounds for these special multigraphs would improve Theorem 7 directly toward $\lfloor \frac{3}{2}\Delta^*\rfloor$.
The reduction implies that a counterexample to the full conjecture, if one exists, must belong to the complement of the good family and must resist every separating cycle of length at most $\Delta^*$; a search for counterexamples can therefore be restricted to graphs whose reductions fall into the 2-face or 2-cut cases of Theorem 3.

Original abstract

A cyclic coloring of a plane graph $G$ is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a plane graph $G$ is its cyclic chromatic number $\chi_c(G)$. Let $\Delta^*(G)$ be the maximum face degree of a graph $G$. In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $\chi_c(G) \leq \lfloor \frac{3}{2}\Delta^*(G)\rfloor$, it is enough to do it for subdivisions of simple $3$-connected plane graphs. We have discovered four new different upper bounds on $\chi_c(G)$ for graphs $G$ from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple $3$-connected plane quadrangulations, and simple $3$-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple $3$-connected plane graphs of maximum degree at least 10, and for subdivisions of simple $3$-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,175 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.42 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.96 · compares with prior results 0.31 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A cyclic coloring of a plane graph $G$ is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a plane graph $G$ is its cyclic chromatic number $\chi_c(G)$. Let $\Delta^*(G)$ be the maximum face degree of a graph $G$. In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $\chi_c(G) \leq \lfloor \frac{3}{2}\Delta^*(G)\rfloor$, it is enough to do it for subdivisions of simple $3$-connected plane graphs. We have discovered four new different upper bounds on $\chi_c(G)$ for graphs $G$ from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple $3$-connected plane quadrangulations, and simple $3$-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple $3$-connected plane graphs of maximum degree at least 10, and for subdivisions of simple $3$-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A cyclic coloring of a plane graph $G$ is a coloring of its vertices such that vertices incident with the same face have distinct colors.	background 1.00	0.05	0.02	asserted 0.99
s1	The minimum number of colors in a cyclic coloring of a plane graph $G$ is its cyclic chromatic number $\chi_c(G)$.	background 1.00	0.07	0.02	asserted 0.99
s2	Let $\Delta^*(G)$ be the maximum face degree of a graph $G$.	background 1.00	0.10	0.02	asserted 0.85
s3	In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $\chi_c(G) \leq \lfloor \frac{3}{2}\Delta^*(G)\rfloor$, it is enough to do it for subdivisions of simple $3$-connected plane graphs.	contribution 0.71	0.92	0.74	asserted 1.00
s4	We have discovered four new different upper bounds on $\chi_c(G)$ for graphs $G$ from this restricted family; three bounds of them are tight.	result 0.85	0.97	0.19	asserted 1.00
s5	As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple $3$-connected plane quadrangulations, and simple $3$-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple $3$-connected plane graphs of maximum degree at least 10, and for subdivisions of simple $3$-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.	result 0.95	0.95	0.36	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (28)

[1]

A. Amini, L. Esperet, J. van den Heuvel: A uniﬁed approach to distance-two colouring of planar graphs, Combinatorica 33 (2013), 253–296

View on Pith 2013
[2]

J. Azarija, R. Erman, D. Král ’ , M. Krnc, L. Stacho: Cyclic colorings of plane graphs with independent faces, European J. Combin. 33 (2012), 249–301

View on Pith 2012
[3]

K. Appel, W. Haken: Every planar graph is four colorable. I. Discharging, Illinois J. Math., 21 (1977), 429–490

View on Pith 1977
[4]

K. Appel, W. Haken: Every planar graph is four colorable. II. Reducibility, Illinois J. Math., 21 (1977), 491–567

View on Pith 1977
[5]

O. V. Borodin: Solution of Ringel’s problems on vertex-f ace coloring of plane graphs and coloring of 1-planar graphs (in Russian), Met. Diskret. Anal. 41 (1984), 12–26

View on Pith 1984
[6]

O. V. Borodin: A new proof of the 6 color theorem, J. Graph T heory 19 (1995), 507–521

View on Pith 1995
[7]

O. V. Borodin: Colorings of plane graphs: A survey, Discr ete Math. 313 (2013), 517–539

View on Pith 2013
[8]

O. V. Borodin, H. J. Broersma, A. Glebov, J. van den Heuvel : A new upper bound on the cyclic chromatic number, J. Graph Theory 54 (2007), 58–72

View on Pith 2007
[9]

O. V. Borodin, D. P. Sanders, Y. Zhao: On cyclic colorings and their generalizations, Discrete Math. 203 (1999), 23–4 0

View on Pith 1999
[10]

O. V. Borodin, D. R. W oodall: Cyclic colorings of 3-polytopes with large maximum face size, SIAM J. Discrete Ma th. 15 (2002), 143–154

View on Pith 2002
[11]

Z. Dvořák, M. Hebdige, F. Hlásek, D. Král ’ , J. A. Noel: Cy clic coloring of plane graphs with maximum face size 16 and 17,arXiv:1603.06722[math.CO] 16 Oct 2017

View on Pith Pith review arXiv 2017
[12]

H. Enomoto, M. Horňák: A general upper bound for the cycl ic chromatic number of 3-connected plane graphs, J. Graph Theory 62 (2009), 1–25

View on Pith 2009
[13]

H. Enomoto, M. Horňák, S. Jendrol ’ : Cyclic chomatic num ber of 3-connected plane graphs, SIAM J. Discrete Math. 14 (2001), 121–137

View on Pith 2001
[14]

F. Havet, D, Král ’ , J.-S. Sereni, R. Škrekovski: Facial colorings using Hall’s theorem, European J. Combin. 31 (201 0), 1001–1019

View on Pith
[15]

F. Havet, J.-S. Sereni, R. Škrekovski: 3-facial colour ings of plane graphs. SIAM J. Discrete Mat. 22 (2008), 231–24 7

View on Pith 2008
[16]

M. Hebdige, D. Král ’ : Third case on the Cyclic Coloring C onjecture, SIAM J. Discrete Math. 30 (2016), 525–548

View on Pith 2016
[17]

M. Horňák, S. Jendrol ’ : On a conjecture by Plummer and To ft, J. Graph Theory 30 (1999), 177–189

View on Pith 1999
[18]

M. Horňák, J. Zlámalová: Another step towards proving a conjecture by Plummer and Toft, Discrete Math. 310 (2010), 442–452

View on Pith 2010
[19]

T. R.Jensen, B. Toft: Graph Coloring Problems, Wiley, N ew York, 1995

View on Pith 1995
[20]

D. Král ’ , T. Madaras, R. Škrekovski: Cyclic, diagonal, and facial coloring, European J. Combin. 26 (2005), 473-490 . 7

View on Pith 2005
[21]

M. Kriesell, Contraction, cycle double cover, and cycl ic coloring in locally connected graphs, J. Combin. Theory S er. B 96 (2006), 881–900

View on Pith 2006
[22]

B. Mohar, C. Thomassen: Graphs on surfaces, The Johns Ho pkins University Press, Baltimore and London, 2001

View on Pith 2001
[23]

O. Ore, M. D. Plummer: Cyclic coloration of plane graphs , in: W. T. Tutte (ed.), Recent progress in combinatorics (Proceedings of the Third W aterloo Conference on Combinato rics, May 1968), Academic Press, 1969

View on Pith 1968
[24]

M. D. Plummer, B. Toft: Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987), 505–515

View on Pith 1987
[25]

D. P. Sanders, Y. Zhao: A new bound on the cyclic chromati c number, J. Combin. Theory, Ser. B 70 (2001), 102–111

View on Pith 2001
[26]

C. E. Shannon: A theorem on coloring the lines of a networ k, J. Math. Phys. 28 (1949), 148–151

View on Pith 1949
[27]

D. B. W est: Introduction to graph theory, Prentice-Hal l Inc. Upper Saddle River, NJ 07458, 2001

View on Pith 2001
[28]

J. Zlámalová: A note on cyclic chromatic number, Discus s. Math. Graph Theory 30 (2010), 115–122. 8

View on Pith 2010

How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

A. Amini, L. Esperet, J. van den Heuvel: A uniﬁed approach to distance-two colouring of planar graphs, Combinatorica 33 (2013), 253–296

View on Pith 2013

[2] [2]

J. Azarija, R. Erman, D. Král ’ , M. Krnc, L. Stacho: Cyclic colorings of plane graphs with independent faces, European J. Combin. 33 (2012), 249–301

View on Pith 2012

[3] [3]

K. Appel, W. Haken: Every planar graph is four colorable. I. Discharging, Illinois J. Math., 21 (1977), 429–490

View on Pith 1977

[4] [4]

K. Appel, W. Haken: Every planar graph is four colorable. II. Reducibility, Illinois J. Math., 21 (1977), 491–567

View on Pith 1977

[5] [5]

O. V. Borodin: Solution of Ringel’s problems on vertex-f ace coloring of plane graphs and coloring of 1-planar graphs (in Russian), Met. Diskret. Anal. 41 (1984), 12–26

View on Pith 1984

[6] [6]

O. V. Borodin: A new proof of the 6 color theorem, J. Graph T heory 19 (1995), 507–521

View on Pith 1995

[7] [7]

O. V. Borodin: Colorings of plane graphs: A survey, Discr ete Math. 313 (2013), 517–539

View on Pith 2013

[8] [8]

O. V. Borodin, H. J. Broersma, A. Glebov, J. van den Heuvel : A new upper bound on the cyclic chromatic number, J. Graph Theory 54 (2007), 58–72

View on Pith 2007

[9] [9]

O. V. Borodin, D. P. Sanders, Y. Zhao: On cyclic colorings and their generalizations, Discrete Math. 203 (1999), 23–4 0

View on Pith 1999

[10] [10]

O. V. Borodin, D. R. W oodall: Cyclic colorings of 3-polytopes with large maximum face size, SIAM J. Discrete Ma th. 15 (2002), 143–154

View on Pith 2002

[11] [11]

Z. Dvořák, M. Hebdige, F. Hlásek, D. Král ’ , J. A. Noel: Cy clic coloring of plane graphs with maximum face size 16 and 17,arXiv:1603.06722[math.CO] 16 Oct 2017

View on Pith Pith review arXiv 2017

[12] [12]

H. Enomoto, M. Horňák: A general upper bound for the cycl ic chromatic number of 3-connected plane graphs, J. Graph Theory 62 (2009), 1–25

View on Pith 2009

[13] [13]

H. Enomoto, M. Horňák, S. Jendrol ’ : Cyclic chomatic num ber of 3-connected plane graphs, SIAM J. Discrete Math. 14 (2001), 121–137

View on Pith 2001

[14] [14]

F. Havet, D, Král ’ , J.-S. Sereni, R. Škrekovski: Facial colorings using Hall’s theorem, European J. Combin. 31 (201 0), 1001–1019

View on Pith

[15] [15]

F. Havet, J.-S. Sereni, R. Škrekovski: 3-facial colour ings of plane graphs. SIAM J. Discrete Mat. 22 (2008), 231–24 7

View on Pith 2008

[16] [16]

M. Hebdige, D. Král ’ : Third case on the Cyclic Coloring C onjecture, SIAM J. Discrete Math. 30 (2016), 525–548

View on Pith 2016

[17] [17]

M. Horňák, S. Jendrol ’ : On a conjecture by Plummer and To ft, J. Graph Theory 30 (1999), 177–189

View on Pith 1999

[18] [18]

M. Horňák, J. Zlámalová: Another step towards proving a conjecture by Plummer and Toft, Discrete Math. 310 (2010), 442–452

View on Pith 2010

[19] [19]

T. R.Jensen, B. Toft: Graph Coloring Problems, Wiley, N ew York, 1995

View on Pith 1995

[20] [20]

D. Král ’ , T. Madaras, R. Škrekovski: Cyclic, diagonal, and facial coloring, European J. Combin. 26 (2005), 473-490 . 7

View on Pith 2005

[21] [21]

M. Kriesell, Contraction, cycle double cover, and cycl ic coloring in locally connected graphs, J. Combin. Theory S er. B 96 (2006), 881–900

View on Pith 2006

[22] [22]

B. Mohar, C. Thomassen: Graphs on surfaces, The Johns Ho pkins University Press, Baltimore and London, 2001

View on Pith 2001

[23] [23]

O. Ore, M. D. Plummer: Cyclic coloration of plane graphs , in: W. T. Tutte (ed.), Recent progress in combinatorics (Proceedings of the Third W aterloo Conference on Combinato rics, May 1968), Academic Press, 1969

View on Pith 1968

[24] [24]

M. D. Plummer, B. Toft: Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987), 505–515

View on Pith 1987

[25] [25]

D. P. Sanders, Y. Zhao: A new bound on the cyclic chromati c number, J. Combin. Theory, Ser. B 70 (2001), 102–111

View on Pith 2001

[26] [26]

C. E. Shannon: A theorem on coloring the lines of a networ k, J. Math. Phys. 28 (1949), 148–151

View on Pith 1949

[27] [27]

D. B. W est: Introduction to graph theory, Prentice-Hal l Inc. Upper Saddle River, NJ 07458, 2001

View on Pith 2001

[28] [28]

J. Zlámalová: A note on cyclic chromatic number, Discus s. Math. Graph Theory 30 (2010), 115–122. 8

View on Pith 2010