Relevant bibliographies by topics / Graphs, planar graphs, five color theorem

Contents

  1. Journal articles
  2. Book chapters
  3. Conference papers

Academic literature on the topic 'Graphs, planar graphs, five color theorem'

Author: Grafiati
Published: 24 April 2022
Last updated: 30 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graphs, planar graphs, five color theorem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Graphs, planar graphs, five color theorem"

1

Liang, Zuosong, and Huandi Wei. "A Linear-Time Algorithm for 4-Coloring Some Classes of Planar Graphs." Computational Intelligence and Neuroscience 2021 (October 5, 2021): 1–5. http://dx.doi.org/10.1155/2021/7667656.

Full text
Abstract:
Every graph G = V , E considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e ∈ E of G with an unordered pair of vertices of G which are called the ends of the edge e . A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k -vertex-coloring of a graph G = V , E is a mapping c : V ⟶ S ( S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar
APA, Harvard, Vancouver, ISO, and other styles
2

BOWLIN, GARRY, and MATTHEW G. BRIN. "COLORING PLANAR GRAPHS VIA COLORED PATHS IN THE ASSOCIAHEDRA." International Journal of Algebra and Computation 23, no. 06 (2013): 1337–418. http://dx.doi.org/10.1142/s0218196713500276.

Full text
Abstract:
Hassler Whitney's theorem of 1931 reduces the task of finding proper, vertex 4-colorings of triangulations of the 2-sphere to finding such colorings for the class ℌ of triangulations of the 2-sphere that have a Hamiltonian circuit. This has been used by Whitney and others from 1936 to the present to find equivalent reformulations of the 4 Color Theorem (4CT). Recently there has been activity to try to use some of these reformulations to find a shorter proof of the 4CT. Every triangulation in ℌ has a dual graph that is a union of two binary trees with the same number of leaves. Elements of a gr
APA, Harvard, Vancouver, ISO, and other styles
3

Bhapkar, H. R., and J. N. Salunke. "Proof of Four Color Map Theorem by Using PRN of Graph." Bulletin of Society for Mathematical Services and Standards 11 (September 2014): 26–30. http://dx.doi.org/10.18052/www.scipress.com/bsmass.11.26.

Full text
Abstract:
This paper intends to study the relation between PRN and chromatic number of planar graphs. In this regard we investigate that isomorphic or 1 isomorphic graph may or may not have equal PRN and few other related results. Precisely, we give simple proof of Four Color Map Theorem.
APA, Harvard, Vancouver, ISO, and other styles
4

XUE, NINI, and BAOYINDURENG WU. "LIST POINT ARBORICITY OF GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 02 (2012): 1250027. http://dx.doi.org/10.1142/s1793830912500279.

Full text
Abstract:
Let G be a graph. The point arboricity of G, denoted by ρ(G), is the minimum number of colors that can be used to color the vertices of G so that each color class induces an acyclic subgraph of G. Borodin et al. (Discrete Math.214 (2000) 101–112) first introduced the list point arboricity of G, denoted by ρl(G). We prove that for any graph G, [Formula: see text], where deg (G) denotes the degeneracy of G, that is, the minimum number k such that δ(H) ≤ k for any subgraph H of G. Using this upper bound, we show that ρl(G) ≤ 3 for any planar graph G. In particular, if either G is K4-minor free, o
APA, Harvard, Vancouver, ISO, and other styles
5

Felsner, Stefan, Hendrik Schrezenmaier, and Raphael Steiner. "Pentagon Contact Representations." Electronic Journal of Combinatorics 25, no. 3 (2018). http://dx.doi.org/10.37236/7216.

Full text
Abstract:
Representations of planar triangulations as contact graphs of a set of internally disjoint homothetic triangles or of a set of internally disjoint homothetic squares have received quite some attention in recent years. In this paper we investigate representations of planar triangulations as contact graphs of a set of internally disjoint homothetic pentagons. Surprisingly such a representation exists for every triangulation whose outer face is a $5$-gon. We relate these representations to five color forests. These combinatorial structures resemble Schnyder woods and transversal structures, respe
APA, Harvard, Vancouver, ISO, and other styles
6

Zhang, Xuanhan. "Attempts and Inferences of the Four-Color Theorem." Science and Technology of Engineering, Chemistry and Environmental Protection 1, no. 10 (2024). https://doi.org/10.61173/xgertb46.

Full text
Abstract:
The Four-Color Theorem is a classic problem in graph theory, stating that any planar map can be colored using no more than four colors so that no adjacent regions share the same color. Since 1976, when Appel and Haken used computer assistance to prove this theorem, it has been considered solved. However, due to its complexity and the difficulty of manually verifying the proof, some mathematicians still have doubts. This study proposes a new logical approach to provide an alternative proof for the Four-Color Theorem. Using a combination of theoretical derivations and graph theory tools, the pap
APA, Harvard, Vancouver, ISO, and other styles
7

Axenovich, Maria, Ursula Schade, Carsten Thomassen, and Torsten Ueckerdt. "Planar Ramsey Graphs." Electronic Journal of Combinatorics 26, no. 4 (2019). http://dx.doi.org/10.37236/8366.

Full text
Abstract:
We say that a graph $H$ is planar unavoidable if there is a planar graph $G$ such that any red/blue coloring of the edges of $G$ contains a monochromatic copy of $H$, otherwise we say that $H$ is planar avoidable. That is, $H$ is planar unavoidable if there is a Ramsey graph for $H$ that is planar. It follows from the Four-Color Theorem and a result of Gonçalves that if a graph is planar unavoidable then it is bipartite and outerplanar. We prove that the cycle on $4$ vertices and any path are planar unavoidable. In addition, we prove that all trees of radius at most $2$ are planar unavoidable
APA, Harvard, Vancouver, ISO, and other styles
8

Aboulker, Pierre, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. "Distributed Coloring in Sparse Graphs with Fewer Colors." Electronic Journal of Combinatorics 26, no. 4 (2019). http://dx.doi.org/10.37236/8395.

Full text
Abstract:
This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring $n$-vertex planar graphs with 7 colors in $O(\lo
APA, Harvard, Vancouver, ISO, and other styles
9

Voigt, Margit, and Arnfried Kemnitz. "A Note on Not-4-List Colorable Planar Graphs." Electronic Journal of Combinatorics 25, no. 2 (2018). http://dx.doi.org/10.37236/7320.

Full text
Abstract:
The Four Color Theorem states that every planar graph is properly 4-colorable. Moreover, it is well known that there are planar graphs that are non-$4$-list colorable. In this paper we investigate a problem combining proper colorings and list colorings. We ask whether the vertex set of every planar graph can be partitioned into two subsets where one subset induces a bipartite graph and the other subset induces a $2$-list colorable graph. We answer this question in the negative strengthening the result on non-$4$-list colorable planar graphs.
APA, Harvard, Vancouver, ISO, and other styles
10

Dębski, Michał, Piotr Micek, Felix Schröder, and Stefan Felsner. "Improved Bounds for Centered Colorings." Advances in Combinatorics, August 16, 2021. http://dx.doi.org/10.19086/aic.27351.

Full text
Abstract:
A vertex coloring $\phi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$ either $\phi$ uses more than $p$ colors on $H$ or there is a color that appears exactly once on $H$. Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function $f$ such that for every $p\geq1$, every graph in the class admits a $p$-centered coloring using at most $f(p)$ colors. In this paper, we give upper bounds for the maximum number of colors needed in a $p$-centered c
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Graphs, planar graphs, five color theorem"

1

Xu, Jin. "Graph Theory Fundamentals." In Maximal Planar Graph Theory and the Four-Color Conjecture. Springer Nature Singapore, 2025. https://doi.org/10.1007/978-981-96-4745-3_1.

Full text
Abstract:
Abstract In this section, we will discuss some of the basic terminologies and concepts of graph theory, which will be assumed throughout the rest of this book, together with a few fundamental properties that characterize planar graphs, e.g., the well-known Kuratowski Theorem and planarity testing algorithm, etc.
APA, Harvard, Vancouver, ISO, and other styles
2

Benjamin, Arthur, Gary Chartrand, and Ping Zhang. "Coloring Graphs." In The Fascinating World of Graph Theory. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691175638.003.0011.

Full text
Abstract:
This chapter considers the concept of coloring the vertices of a graph by focusing on the Four Color Problem. It begins with a discussion of three mathematics problems that involve conjecture, attributed to Pierre Fermat, Leonhard Euler, and Christian Goldbach. It then examines one of the most famous problems in mathematics, the Four Color Problem, which addresses the question of whether it is always possible to color the regions of every map with four colors so that neighboring regions are colored differently. After an overview of the origins of the Four Color Problem, the chapter goes on to
APA, Harvard, Vancouver, ISO, and other styles
3

Benjamin, Arthur, Gary Chartrand, and Ping Zhang. "Synchronizing Graphs." In The Fascinating World of Graph Theory. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691175638.003.0012.

Full text
Abstract:
This chapter considers a new type of graph coloring known as edge coloring. It begins with a discussion of an idea by Scottish physicist Peter Guthrie Tait that led to edge coloring. Tait proved that the regions of every 3-regular bridgeless planar graph could be colored with four or fewer colors if and only if the edges of such a graph could be colored with three colors so that every two adjacent edges are colored differently. Tait thought that he had found a new way to solve the Four Color Problem. The chapter also examines the chromatic index of a graph, Vizing's Theorem, applications of ed
APA, Harvard, Vancouver, ISO, and other styles
4

Benjamin, Arthur, Gary Chartrand, and Ping Zhang. "Classifying Graphs." In The Fascinating World of Graph Theory. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691175638.003.0002.

Full text
Abstract:
This chapter considers the richness of mathematics and mathematicians' responses to it, with a particular focus on various types of graphs. It begins with a discussion of theorems from many areas of mathematics that have been judged among the most beautiful, including the Euler Polyhedron Formula; the number of primes is infinite; there are five regular polyhedra; there is no rational number whose square is 2; and the Four Color Theorem. The chapter proceeds by describing regular graphs, irregular graphs, irregular multigraphs and weighted graphs, subgraphs, and isomorphic graphs. It also anal
APA, Harvard, Vancouver, ISO, and other styles
5

Benjamin, Arthur, Gary Chartrand, and Ping Zhang. "Introducing Graphs." In The Fascinating World of Graph Theory. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691175638.003.0001.

Full text
Abstract:
This chapter provides an introduction to graphs, a mathematical structure for visualizing, analyzing, and generalizing a situation or problem. It first consider four problems that have a distinct mathematical flavor: the Problem of the Five Princes, the Three Houses and Three Utilities Problem, the Three Friends or Three Strangers Problem, and the Job-Hunters Problem. This is followed by discussion of four problems that are not only important in the history of graph theory, but which led to new areas within graph theory: the Königsberg Bridge Problem, the Four Color Problem, the Polyhedron Pro
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graphs, planar graphs, five color theorem"

1

Inoue, Yuta, Ken-Ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, and Tomohiro Sonobe. "Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem." In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2024. http://dx.doi.org/10.1109/focs61266.2024.00016.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graphs, planar graphs, five color theorem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography