3
$\begingroup$

Given a graph, is it always possible to color the edges of the graph using two colors such that there exists an embedding of the graph in the plane where only opposite-colored edges cross?

Simple counting arguments from lower bounds on the pair-crossing number have failed me so far; I have also not had luck finding information on graphs with maximal crossing number for a given number edges.

Extension: if it is not always possible with two colors, what is the minimal number of colors required such that it is always possible? Is it constant?

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ It is not always possible with two colours since an $n$-vertex planar graph has at most $3n-6$ edges, and the red subgraph and blue subgraph are both planar graphs. So, any $n$-vertex graph with at least $6n-11$ edges is a counterexample. $\endgroup$
    – Tony Huynh
    Commented Dec 4, 2023 at 0:49
  • 1
    $\begingroup$ Seems related to graph thickness? $\endgroup$
    – Jukka Kohonen
    Commented Dec 4, 2023 at 0:54
  • $\begingroup$ I think the minimum number of colours is sometimes called geometric thickness. $\endgroup$
    – Tony Huynh
    Commented Dec 4, 2023 at 1:10
  • $\begingroup$ Ah yes, thinking of it as the union of planar subgraphs does make the structure of the problem much clearer. Seems obvious now, but thank you for the tip $\endgroup$
    – Tjaden Hess
    Commented Dec 4, 2023 at 1:12
  • 1
    $\begingroup$ Ramsey's theorem tells us that for any fixed number of colors a sufficiently large complete graph will contain a monochromatic $K_5$. $\endgroup$
    – bof
    Commented Dec 4, 2023 at 13:17

1 Answer 1

Reset to default
4
$\begingroup$

As requested by Jukka Kohonen, I'll turn my comment into an answer.

The answer is in general no. If such an embedding exists, then the red subgraph and blue subgraph are both planar. However, every $n$-vertex planar graph has at most $3n-6$ edges. So, any $n$-vertex graph with at least $6n-11$ edges is a counterexample.

The minimum number of colours required for such an embedding is often called geometric thickness. For example, geometric thickness is mentioned on the Wikipedia page for graph thickness, which is the minimum number of planar subgraphs that partition the edge set of a graph (where the embedding is not necessarily the same for each planar subgraph).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Does it make a difference if the vertex positions are required to be the same in the two embeddings? This would better match the OP's problem statement. $\endgroup$
    – Jukka Kohonen
    Commented Dec 4, 2023 at 11:52
  • 1
    $\begingroup$ Yes, it makes a difference. Geometric thickness is what the OP is asking about, while thickness is a related but different parameter (since the embeddings do not have to be the same). $\endgroup$
    – Tony Huynh
    Commented Dec 4, 2023 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .