6
$\begingroup$

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

Improve this question
$\endgroup$
12
  • $\begingroup$ What is "circle"? Is it the same as "color", or "label"? $\endgroup$
    – Fedor Petrov
    Commented Apr 28, 2023 at 10:42
  • $\begingroup$ @FedorPetrov An edge may have a label like $\{1,2\}$ on it. When we circle, we only circle one number at a time, like $1$. ("Circle" here is used as a verb, as in "circle the correct answer") $\endgroup$
    – Karo
    Commented Apr 28, 2023 at 12:43
  • $\begingroup$ It is not clear from the question whether you allow both numbers to be circled on a single edge. If not, then a graph with a single edge is a counterexample, so I suppose that you allow it. An example that achieves $3k/2$ is given by a $K_4$ where non-adjacent edges receive the same labels. $\endgroup$
    – domotorp
    Commented Apr 30, 2023 at 14:40
  • $\begingroup$ @domotorp It is indeed allowed. $\endgroup$
    – Karo
    Commented Apr 30, 2023 at 15:10
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4698545/… $\endgroup$
    – RobPratt
    Commented May 17, 2023 at 18:54

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .