<p>Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is <em>Gallai-colored</em> if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may then define the polytope $\mathcal{P}(G) \subseteq \mathbf{R}^V$ by:</p>

<blockquote>
  <p>$0 \leq f(x)$ for every $x \in V$,</p>
  
  <p>$\sum_{x \in S} f(x) \leq c_i$ for every monochromatic set $S$ with color $i$.</p>
</blockquote>

<p>We say that $G$ is <em>perfectly Gallai-colored</em> if the polytope $\mathcal{P}(G)$ is integral for every tuple $c$ with integral values. In particular, for two colors it includes graphs for which the clique-packing / independent-packing problems are LP-solvable. Among those are the comparability and co-comparability graphs, as this should follow by the Greene-Kleitman theorem if I'm correct.</p>

<p>I have two questions in this respect:</p>

<p>(1) Are there existing references to this class in the literature?</p>

<p>(2) Is this class closed under the operation of substitution? If true this would imply that a completely decomposable colored graph is perfectly-Gallai colored. This would generalize the fact that a cograph is both comparability and co-comparability.</p>

CC BY-SA 3.0
2014-04-23T13:09:22.510Z
I think, I didn't get the question completely, but what happens for $\mathcal{P}$ when $c=(1,\ldots,1)$, Is there even exists such a polytope when $k < |V|$?
Saeed
CC BY-SA 3.0
2014-04-23T13:41:37.280Z
For $c = (1,\ldots,1)$ the polytope is $[0,1]^n$, this case is somewhat trivial since it doesn't take into account the edge of the graphs - you need to consider sets of size at least 2 for this. If by 'existence' of the polytope you mean that both $\mathcal{P}$ and $\bar{\mathcal{P}}$ are non-empty, then it seems clear: $(0,\ldots,0) \in \mathcal{P}$ and $(c,\ldots,c) \notin \mathcal{P}$ with $c = \max_i c_i$.
NisaiVloot
CC BY-SA 3.0
2014-04-23T18:24:30.577Z
Is $S$ a set of vertices? When is a set of vertices monochromatic? If their induced subgraph is monochromatic?
domotorp
CC BY-SA 3.0
2014-04-23T20:17:50.223Z
I was expecting a set $S \subseteq V$ to be monochromatic if the coloring function is constant on $[S]^2$ (which is essentially your suggestion). Though, I can't tell if this is the proper definition in this context.
NisaiVloot
CC BY-SA 3.0
2014-04-23T20:41:44.847Z
The confusing part for me was that I thought $S$ is a set of edges as otherwise I couldn't understand what does even your latest sentence in the comments means. You assigned color to edges not vertices and I think everyone defines G=(V,E) not something like G=(V'(E),E). Then definition of polytope, f, ... are somehow confusing, at least for me even for the trivial cases.
Saeed
<reference-request><graph-colouring><polytope>
An interesting class of colored graphs?
NisaiVloot
# An interesting class of colored graphs?

(Asked by: username_0 on 2014-04-23)

Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is *Gallai-colored* if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c\_1,\ldots,c\_k)$. We may then define the polytope $\mathcal{P}(G) \subseteq \mathbf{R}^V$ by:

> $0 \leq f(x)$ for every $x \in V$,
>
> $\sum\_{x \in S} f(x) \leq c\_i$ for every monochromatic set $S$ with color $i$.

We say that $G$ is *perfectly Gallai-colored* if the polytope $\mathcal{P}(G)$ is integral for every tuple $c$ with integral values. In particular, for two colors it includes graphs for which the clique-packing / independent-packing problems are LP-solvable. Among those are the comparability and co-comparability graphs, as this should follow by the Greene-Kleitman theorem if I'm correct.

I have two questions in this respect:

(1) Are there existing references to this class in the literature?

(2) Is this class closed under the operation of substitution? If true this would imply that a completely decomposable colored graph is perfectly-Gallai colored. This would generalize the fact that a cograph is both comparability and co-comparability.

**Tags:** reference-request, graph-colouring, polytope
> **Comments:**
> **username_1**: I think, I didn't get the question completely, but what happens for $\mathcal{P}$ when $c=(1,\ldots,1)$, Is there even exists such a polytope when $k < |V|$?  
> **username_0**: For $c = (1,\ldots,1)$ the polytope is $[0,1]^n$, this case is somewhat trivial since it doesn't take into account the edge of the graphs - you need to consider sets of size at least 2 for this. If by 'existence' of the polytope you mean that both $\mathcal{P}$ and $\bar{\mathcal{P}}$ are non-empty, then it seems clear: $(0,\ldots,0) \in \mathcal{P}$ and $(c,\ldots,c) \notin \mathcal{P}$ with $c = \max_i c_i$.  
> **username_2**: Is $S$ a set of vertices? When is a set of vertices monochromatic? If their induced subgraph is monochromatic?  
> **username_0**: I was expecting a set $S \subseteq V$ to be monochromatic if the coloring function is constant on $[S]^2$ (which is essentially your suggestion). Though, I can't tell if this is the proper definition in this context.  
> **username_1**: The confusing part for me was that I thought $S$ is a set of edges as otherwise I couldn't understand what does even your latest sentence in the comments means. You assigned color to edges not vertices and I think everyone defines G=(V,E) not something like G=(V'(E),E). Then definition of polytope, f, ... are somehow confusing, at least for me even for the trivial cases.  

---

## 0 answers

