All Questions
Tagged with planar-graphs coloring
95
questions
0
votes
0
answers
31
views
Does there exist a 5-connected planar graph that is perfect?
In a previous post, I proved that no 5-connected maximal planar graph is perfect.
My proof, with slight modifications, can show that if a maximal planar graph with minimum degree 5 is perfect, then ...
- 2,474
2
votes
1
answer
81
views
Does there exist a 5-connected maximal planar graph that is perfect?
A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any
induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)
For maximal planar graphs with connectivity 3, it is easy to ...
- 2,474
1
vote
1
answer
55
views
Are there examples of non-perfect graphs among these graphs
A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any
induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)
Start with a simple planar graph $H$ where every face is a 4-cycle. ...
- 2,474
2
votes
1
answer
51
views
Every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
I'm trying to prove that every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
However, I have no opportunity to receive any validation or correction on it, but it would be very ...
- 123
0
votes
1
answer
73
views
Irrigation problem as a graph coloring problem
I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem.
The graph is a $12 \times 12$ grid, representing a field. The field needs to be ...
- 137
0
votes
0
answers
42
views
Why can we assume a triangulated graph without loss of generality, for proofs of the 4 colour theorem?
In the Wikipedia article about the four colour theorem it is stated
First, if planar regions separated by the graph are not triangulated, i.e. do not have exactly three edges in their boundaries, we ...
- 1,125
0
votes
2
answers
135
views
Where does my short proof of the 4-colour theorem go amiss?
The proof is essentially a generalisation of the $5$-Colour Theorem:
Proof. Consider the set $S$ of planar graphs which are not $4$-colourable. Choose the graph $G \in S$ that has the least number of ...
- 392
0
votes
0
answers
26
views
Bounds on chromatic number in terms of chromatic numbers of subgraphs.
Suppose we have a graph G of the form $G = G1 \cup G2$, and graphs G1 and G2 are defined by $V(G1) = V(G2)$. How can we describe the dynamics of the chromatic number of G in relation to the chromatic ...
- 115
2
votes
1
answer
119
views
Construct a class of $n$-vertex maximal planar graphs with chromatic number 4 and independence number $\lceil \frac{n}{4} \rceil + 1$
An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of largest possible size for a given graph $G$. This size is called ...
- 2,474
0
votes
0
answers
52
views
A graph coloring game of merging subgraphs
A graph coloring game
This is a 2-player game played by players $A$ and $B$. A random non-trivial planar connected graph $G(V,E)$ is chosen. Player $A$ sets up the game as follows:
Player $A$ ...
- 3,341
2
votes
1
answer
264
views
4-color coloring game.
Similar to this question.
5-color coloring game.
Let there be two players, $𝐴$ and $𝐵$, and a map.
They now play a game such that:
Player $𝐴$ picks a region and player $𝐵$ colors it such that the ...
- 796
3
votes
1
answer
151
views
Prove that regions formed by a planar map vertices even degree can be colored with two colors such that no two neighboring regions have the same color
Prove that regions formed by a planar map all of whose vertices have
even degree can be colored with two colors such that no two
neighboring regions have the same color.
I would like a proof using ...
- 450
0
votes
0
answers
76
views
Proving the 4-color theorem. [duplicate]
I have a question as to why the four color theorem has not been proved by hand.
I believe that to prove the four color theorem, it suffices to show that a complete graph may only be planar if it has 4 ...
- 1
4
votes
2
answers
124
views
Proving a chromatic number upper bound for a graph with a planar subgraph
I have the following problem:
Let $G$ be a graph such that for any partition of its vertices into two sets, the induced subgraph on either of the sets is going to be planar. Prove that $\chi(G) \leq ...
- 125
1
vote
1
answer
558
views
A question about the four-color problem
I remember there was a theorem in the history, concerning the four-color problem. It states something like following: in a map, the maximal number of regions that can be neighbors to each other is 4. ...
- 133