# All Questions

Tagged with graph-theory co.combinatorics

1,481
questions

**1**

vote

**0**answers

38 views

### Coloration of an interval graph with constraints [on hold]

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...

**0**

votes

**0**answers

34 views

### Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs

Finding regular $\mathrm{f}$-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms ...

**-2**

votes

**0**answers

45 views

### Polya Enumeration to study proper graph colorings

Can Polya enumeration technique or its modification be used in evaluating the chromatic polynomial of a simple graph?
Specifically, we have to ensure that two distinct points have distinct colors if ...

**4**

votes

**0**answers

199 views

### Reference for results about planar graphs

A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...

**20**

votes

**3**answers

713 views

### When can a graph be oriented to form a Hasse diagram of a finite poset?

For any finite poset $P=(X,\leq)$ there is an undirected graph $G$ underlying the Hasse diagram of $P$ such that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...

**8**

votes

**0**answers

235 views

+50

### Connected subgraphs and their sums

Let $G=(V,E)$ be an undirected graph with $|V|\geq 4$ such that for any distinct vertices $a_1,a_2,b_1,b_2$, there is a path from $a_1$ to $a_2$ and a (vertex-)disjoint path from $b_1$ to $b_2$.
...

**2**

votes

**1**answer

119 views

### Edge coloring graphs is in P?

It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...

**1**

vote

**1**answer

58 views

### Perfect graphs condition could be weakened?

The perfect graphs are generally defined as those graphs whose every induced subgraph has its chromatic number equal to its clique number.
Now,are there some examples where the clique number of graph ...

**1**

vote

**0**answers

81 views

### Chromatic number of certain graphs with high maximum degree

Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...

**2**

votes

**0**answers

177 views

### Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?

As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$.
According to the Dynamic Survey of Ramsey Numbers at ...

**6**

votes

**0**answers

105 views

### Squared squares and partitions of $K_{nn}$

This is inspired by a recent question.
Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...

**15**

votes

**7**answers

972 views

### Examples of proofs by making reduction to a finite set [closed]

This is a very abstract question, I hope this is appropriate.
Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...

**3**

votes

**1**answer

156 views

### Diameter of Cayley graphs of finite simple groups

Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...

**11**

votes

**4**answers

452 views

### A specific collection of subgraphs in $K_{70, 70}$

Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:
1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;
2)Any ...

**4**

votes

**0**answers

77 views

### Dinitz Conjecture extension to rectangles

The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...