The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
297 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
28
votes
0answers
827 views

Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
8
votes
0answers
1k views

a new lower bound for the chromatic number of a graph?

Let S+(G) denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph G. Let S-(G) denote the sum of the squares of the negative eigenvalues and q the chromatic ...
7
votes
0answers
146 views

Colouring a graph whose edge set is a special union of cliques

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
7
votes
0answers
227 views

A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now. The setup is as follows. We have a vertex set partitioned in to sets ...
6
votes
0answers
128 views

The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...
6
votes
0answers
236 views

Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)

Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be? The Chvátal graph has ...
6
votes
0answers
330 views

What is this subclass of $k$-colorable graphs called?

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs. Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows. ...
3
votes
0answers
70 views

Independence Number of K4-free planar graphs

The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. ...
3
votes
0answers
75 views

Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...
2
votes
0answers
160 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
2
votes
0answers
120 views

Clique number of a $k$th power of a graph in terms of maximum degree?

Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better than the bound on the ...
2
votes
0answers
176 views

Maximum number of 4-colorings of planar graphs (precise version)

This is a redo of my earlier question. I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page. For a fixed $n$, what is known (references preferred) about the ...
2
votes
0answers
131 views

finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply. Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...
1
vote
0answers
81 views

Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com: http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using ...
1
vote
0answers
83 views

3-edge-coloring of 3-regular multigraphs

Given that a 3-regular multigraph is 3-edge-colorable, is there an expression for how many 3-edge-colorings exist? (For example, if a 2-regular multigraph is 2-edge-colorable, there are $2^k$ ...
0
votes
0answers
69 views

asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question. Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf Namely theorem 5. Now, feel ...
0
votes
0answers
26 views

number of bipolar orientations to acyclic ones

Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has? I am trying to show that the number of bipolar orientations is much much lower than the ...
0
votes
0answers
162 views

A copy of the Vizing's classic article about List Coloring.

Does anyone know where I get a copy of the Vizing's classic article about List Coloring? "V. G. Vizing, Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i ...
0
votes
0answers
195 views

r-chromatic graphs with sufficient girth

Hi. For k,l positive integers let h(k,l) be the least integer with the property that in graph on h(k,l) vertices either there is a closed circuit of k or fewer lines or that the graph contains l ...