7

The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019 Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.


6

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891. Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be ...


5

While I know nothing about these measures, quick googling led me to the paper Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, André Kündgen, Radhika Ramamurthi: Coloring with no $2$-colored $P_4$’s, Electronic Journal of Combinatorics 11 (2004), no. 1, art. no. R26, doi: 10.37236/1779. They prove that $\chi_s(G)\le\chi_a(G)\bigl(2\chi_a(G)-1\bigr)$ ...


3

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name injective coloring. An injective colouring of a graph $G$ is a colouring $...


3

(Copied from a comment:) If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".


3

I would call this a polychromatic coloring of the closed neighborhood hypergraph. I don't think this has been studied before for general graphs. Here is a paper studying the question when edges are colored: Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex Scott: Cover-Decomposition and Polychromatic Numbers And here is one that studies the conflict-free ...


3

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then ...


2

This result is included in Ore's book The Four-Colour Problem (see Theorem 7.4.3). I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)$\implies$(i). It seems that at that time, it wasn't known that the mapping $f\longmapsto f^*$ is a bijection. Sorry to disappoint; but that's the best I ...


2

One always has $\chi(G+M)\leq 2\chi(G)$, and this bound does not seem improvable in general. To see the bound itself, note that the only edges of the matching $M$ that can possibly ruin an optimal coloring of $G$ are those between two vertices of the same color class; in particular, we can color $G+M$ by simply creating two new colors for every original ...


2

It is studied in the literature. It is the coloring variant called fall coloring introduced by Dunbar et al [1]. Quote from [1] (I have made minute changes in the language): A coloring of a graph $G=(V,E)$ is a partition $\Pi=\{V_1,V_2,\dots,V_k\}$ of the vertices of G into independent sets $V_i$, or color classes. A vertex $v\in V_i$ is called colorful if ...


2

$L(p,q)$ coloring is a function V $\rightarrow \mathbb{N}$ such that the labels on vertices at distance 1 differ by at least $p$ and vertices at distance 2 differ by at least $q$. Special labelling looks like $L(0,1)$ coloring.


2

I don't know if this problem has another name, but it seems like it's easy to solve. We first see that a weak incidence coloring of a graph $G$ corresponds to an edge coloring of the graph $G'$ obtained by subdividing each edge of $G$ once. This, in turn, corresponds to a vertex coloring of $L(G')$, the line graph of $G'$. This line graph consists of a ...


1

The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction. Also, the reduction $k$-COLORABILITY $\leq_p$ $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$) given by Emden-Weinert ...


1

I think under typical terminology this would be called "Min k-Uncut" (note, Min Uncut asks for a partition into two that minimizes the number of edges not cut, and Max k-Uncut asks for a k partition maximizing the number of uncut edges). Googling seems to find some references.


1

Conjecture 2 is already proved. Quote from J.A. Tilley, The a-graph coloring problem(2017): Theorem A.1. Let $G$ be an a-graph with boundary cycle $uxvy$ for the exterior 4-face and let $G$ have a 4-coloring $c$. Suppose, without loss of generality, that $c(x)=1$, $c(y)=1$ or 2, $c(u)=3$, and $c(v)=3$ or 4. Then there is either a 1–2 path between $x$ and $y$...


Only top voted, non community-wiki answers of a minimum length are eligible