The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
152 views

Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
1
vote
1answer
76 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
2
votes
1answer
93 views

How to construct a graph with arbitrarily large girth and large chromatic number? [closed]

Erdos theorem says it is possible and it is not so easy. What is the general procedure to construct graphs like Grötzsch graph?
6
votes
0answers
125 views

Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
12
votes
1answer
253 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
1
vote
0answers
35 views

Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
29
votes
8answers
2k views

Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...
5
votes
1answer
345 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 ...
6
votes
0answers
108 views

What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...
0
votes
2answers
87 views

Coloring of a normal map

can the following proposition be proved? If so please suggest a method. Can Kempe’s Argument be used for proof ? Proposition: A normal map has a colouring of countries by 4 colours iff the edges of ...
8
votes
1answer
329 views

Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...
0
votes
2answers
50 views

Coloring maximal independent sets with 1 color

Let $G$ be a graph and $M\subseteq V(G)$ be a maximal independent set. Is there a coloring $c:V(G)\to\chi(G)$ such that $c$ is constant on $M$? (The answer is positive for graphs with infinite ...
1
vote
2answers
80 views

Regular graphs with strongly regular edge colorings

Given a positive integer $c>1$, for what parameters $(v,k,\lambda,\mu)$ does there exist a $c k$ regular graph on $v$ vertices that can be given an edge coloring with $c$ colors, such that the ...
0
votes
1answer
176 views

Coin graph is 4-colorable

How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.
2
votes
1answer
196 views

On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements. We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...
3
votes
1answer
79 views

Coloring graph such that the coloring classes are not maximal independent sets

Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have ...
1
vote
0answers
122 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 ...
6
votes
2answers
263 views

Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$). For odd integers $n$ we have $n=\chi(K_n) = ...
2
votes
0answers
182 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 ...
0
votes
0answers
75 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 ...
34
votes
6answers
3k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
6
votes
2answers
206 views

Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index. Based on limited experiments (up to 8 vertices and few larger graphs), I suspect: Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...
8
votes
1answer
335 views

Postnikov's approach to perfect matchings of graphs

Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
6
votes
0answers
140 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$ ...
7
votes
2answers
136 views

Bounds on chromatic number of $k$-planar graphs

A $1$-planar graph can be drawn in the plane so that each arc is crossed at most once by another arc. A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times. Planar graphs are ...
0
votes
0answers
30 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 ...
4
votes
2answers
131 views

Is There a Graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free

Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nesetril and Rodl proved that for a graph $G$, there exists a graph $F\to G$ with ...
3
votes
1answer
59 views

Graph construction to double coloring & Hadwiger number

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$. Is there for every graph $G$ a graph $2G$ such that -- $\chi(2G) = 2\chi(G)$, and -- $\eta(2G) = 2\eta(G)$? For each one of the above ...
3
votes
0answers
81 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$. ...
10
votes
2answers
179 views

Big Mono-Chromatic Subgraphs of Vertex 2-Colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V ...
10
votes
9answers
2k views

What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...
8
votes
2answers
509 views

Derivative of Tutte polynomial at -1

Let Tutte polynomial on graph with edge-set $E$ be defined as follows $$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$ Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of ...
5
votes
2answers
257 views

Fractional chromatic number, find reference to a particular alternate definition for

I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs. Let me review the most common definition and basic properties first. Let $ G $ be ...
3
votes
3answers
217 views

Crystal structure, lattice, Graph and coloring

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field. Given a periodic graph (actually a physical ...
13
votes
3answers
682 views

Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant of the integer lattice $\mathbb{Z}^2$, and from each site $s \in S$, one connects $s$ to every lattice point to which it has a ...
2
votes
1answer
188 views

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
3
votes
1answer
68 views

How to prove a certain connection between the list-chromatic number of a bipartite graph and a cardinal?

Let $G=(L,R,E)$ be a complete bipartite graph, such that $|L|=\aleph_0$ and $|R|=\kappa$. I'd like to show that if $\kappa<2^{\aleph_0}$ then the list-chromatic number of $G$ can't be more than ...
2
votes
1answer
302 views

bipartite graph coloring

Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...
3
votes
0answers
77 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 ...
10
votes
1answer
321 views

Coloring $K_n$ via edge-weight sums

This is a question inspired by and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly much easier! Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each edge ...
6
votes
1answer
254 views

What is the status of this strong form of Hedetniemi's conjecture?

In this question, a graph is a finite, undirected graph without loops or multiple edges, and a colouring of a graph is a proper vertex colouring. The product $G \times H$ of graphs $G$ and $H$ is the ...
16
votes
1answer
678 views

A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...
5
votes
1answer
306 views

coloring in lattice

This is a mathematical question raised from engineering and physics: Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...
2
votes
1answer
106 views

Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice

Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can ...
2
votes
3answers
624 views

4-colorable graphs

Hey guys, I tried to find a solution to this in the web but couldn't. Can you tell me if the following sentence is correct or else give me a counterexample? G is 4-colorable iff each sub-graph G' in G ...
1
vote
1answer
246 views

When does graph Laplacian have eigenvalue -1?

Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...
7
votes
0answers
154 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 ...
20
votes
3answers
1k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
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 ...
9
votes
2answers
428 views

Labelled spanning trees without edge crossings

Draw the complete graph $K_n$ on a plane in general position with every edge a straight line and randomly label the edges $0$ or $1$. Does this graph always have a spanning tree with no edges crossing ...