A survey on the cyclic coloring and its relaxations
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)
A planar graph \(G\) can have more different planar embeddings called also plane drawings of \(G\). Every plane drawing is called a plane graph. Edges of a plane graph separate the plane into regions called faces. A coloring \(c:V(G)\rightarrow\{1,\dots,k\}\) of a plane graph \(G\) is called cyclic if \(c(u)\neq c(v)\) for every two vertices \(u\) and \(v\) that belong to a common face. The minimum \(k\) for which there exists a cyclic coloring of a plane graph \(G\) is called the cyclic chromatic number of \(G\) and is denoted by \(\chi_c(G)\). This work bring an exhaustive overview of upper bounds on \(\chi_c(G)\) in the first part. Later, several relaxations are treated. In particular, facial rainbow colorings, \(\ell\)-facial colorings, odd colorings, unique-maximum colorings, cyclic edge colorings, facial rainbow edge colorings, \(\ell\)-facial edge colorings, odd edge colorings and unique-maximum edge colorings are presented together with several results about their chromatic numbers.
- 3-Facial Coloring of Plane Graphs
- -facial edge colorings of graphs
- A counterexample to a conjecture on facial unique-maximal colorings
- A general upper bound for the cyclic chromatic number of 3-connected plane graphs
- A new bound on the cyclic chromatic number
- A new proof of the 6 color theorem
- A new upper bound on the cyclic chromatic number
- A note on 2-facial coloring of plane graphs
- A note on cyclic chromatic number
- A note on graphs of class I
- A sufficient condition for a planar graph to be class I
- A sufficient condition for a plane graph with maximum degree 6 to be class 1
- A Theorem on Coloring the Lines of a Network
- A unified approach to distance-two colouring of graphs on surfaces
- An improved bound on parity vertex colourings of outerplane graphs
- Another step towards proving a conjecture by Plummer and Toft
- Coloring of plane graphs with unique maximal colors on faces
- Colouring vertices of plane graphs under restrictions given by faces
- Contractions, cycle double covers, and cyclic colorings in locally connected graphs
- Cyclic chromatic number of 3-connected plane graphs
- Cyclic coloration of 3-polytopes
- Cyclic coloring of plane graphs
- Cyclic coloring of plane graphs with maximum face size 16 and 17
- Cyclic colorings of 3-polytopes with large maximum face size
- Cyclic colorings of plane graphs with independent faces
- Cyclic degree and cyclic coloring of 3-polytopes
- Cyclic, diagonal and facial colorings
- Cyclic, diagonal and facial colorings -- a missing case
- Decompositions of plane graphs under parity constrains given by faces
- Edge coloring of planar graphs which any two short cycles are adjacent at most once
- Edge coloring of planar graphs without adjacent 7-cycles
- Edge colorings of planar graphs without 5-cycles with two chords
- Edge colorings of planar graphs without 6-cycles with three chords
- Edge colorings of planar graphs without adjacent special cycles.
- Every planar map is four colorable
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Facial colorings using Hall's theorem
- Facial parity 9-edge-coloring of outerplane graphs
- Facial parity edge coloring of outerplane graphs
- Facial parity edge colouring
- Facial parity edge colouring of plane pseudographs
- Facial rainbow coloring of plane graphs
- Facial rainbow colorings of trees
- Facial rainbow edge-coloring of plane graphs
- Facial rainbow edge-coloring of simple 3-connected plane graphs
- Facial unique-maximum colorings of plane graphs with restriction on big vertices
- Graphs on surfaces
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3900784 (Why is no real title available?)
- scientific article; zbMATH DE number 1275149 (Why is no real title available?)
- scientific article; zbMATH DE number 6945774 (Why is no real title available?)
- scientific article; zbMATH DE number 3273761 (Why is no real title available?)
- scientific article; zbMATH DE number 3310750 (Why is no real title available?)
- Improved bound on facial parity edge coloring
- Improved bounds for some facially constrained colorings
- List 2-facial 5-colorability of plane graphs with girth at least 12
- List-Coloring Squares of Sparse Subcubic Graphs
- On cyclic colorings and their generalizations
- On facial unique-maximum (edge-)coloring
- On the cyclic coloring conjecture
- On the strong parity chromatic number
- On vertex types and cyclic colourings of 3-connected plane graphs
- Parity vertex coloring of outerplane graphs
- Parity vertex colouring of plane graphs
- Planar graphs of maximum degree seven are Class I
- Planar graphs of maximum degree six without 7-cycles are class one
- Some sufficient conditions for a planar graph of maximum degree six to be Class 1
- Strong parity vertex coloring of plane graphs
- The four-colour theorem
- The square of a planar cubic graph is 7-colorable
- Third case of the cyclic coloring conjecture
- Topological graph theory.
- Unavoidable set of face types for planar maps
- Unique-maximum coloring of plane graphs
- Unique-maximum edge-colouring of plane graphs with respect to faces
- 3-facial edge-coloring of plane graphs
- scientific article; zbMATH DE number 125449 (Why is no real title available?)
- scientific article; zbMATH DE number 1454643 (Why is no real title available?)
- Edge homogeneous colorings
- A note on the facial edge-coloring conjecture
- Facial matchings in plane graphs
- On a 3-coloring of plane graphs without monochromatic facial 3-paths
This page was built for publication: A survey on the cyclic coloring and its relaxations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2214302)
