Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
625
questions
11
votes
2
answers
276
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 \...
- 647
11
votes
2
answers
814
views
Graphs with the same chromatic symmetric function
Does anyone know more examples of two nonisomorphic connected graphs with the same chromatic symmetric function? The only pair I know is the one in Stanley's paper on c.s.f.'s [http://math.mit.edu/~...
- 1,440
11
votes
3
answers
2k
views
Do you know a faster algorithm to color planar graphs?
while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be ...
- 351
11
votes
1
answer
267
views
What is the chromatic number of the "conic hypergraph" on a non-singular plane cubic?
Can we color the points of a complex non-singular plane cubic curve with finitely many colors so that no conic intersects the curve at 6 distinct points of the same color?
If so, what is the smallest ...
- 85.1k
11
votes
1
answer
236
views
A variant of Nelson-Hadwiger Problem on the chromatic number of the plane
The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \ $ form an edge iff $a_1-a_2$...
- 6,084
11
votes
1
answer
800
views
Graphs with only disjoint perfect matchings, with coloring
The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...
- 155
11
votes
1
answer
416
views
Chromatic number of Voronoi diagrams of lattices
Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have ...
- 30.1k
11
votes
1
answer
357
views
Graph chromatic numbers defined by interactive proof
Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following
Short form of the question: Let $G$ be a finite graph (undirected and without self-...
- 30.1k
11
votes
1
answer
364
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 ...
- 2,541
11
votes
0
answers
225
views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
- 211
10
votes
2
answers
702
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 ...
- 149k
10
votes
3
answers
478
views
How many colors do we need to avoid bichromatic triangles?
Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors.
I wonder if the following type of question has ...
- 18.4k
10
votes
2
answers
465
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 ...
- 1,160
10
votes
1
answer
361
views
When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?
Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...
- 2,506
10
votes
2
answers
801
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 ...
- 2,380
10
votes
2
answers
443
views
Conjecture on minimum size of graph
Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
- 225
10
votes
1
answer
796
views
Which lattices have more than one minimal periodic coloring?
The lattice $\mathbb{Z}^n$ has an essentially unique (up to permutation) minimal periodic coloring for all $n$, namely the "checkerboard" 2-coloring. Here a coloring of a lattice $L$ is a coloring of ...
- 15.3k
10
votes
1
answer
215
views
Kneser subgraph with high chromatic number
For positive integers $n\geq 2k$, it is known that the chromatic number of the Kneser graph $K_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S_{n,k}$ (definition in the same link), which is a ...
- 223
10
votes
2
answers
575
views
Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6?
Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that ...
- 18.4k
10
votes
1
answer
884
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
- 1,258
10
votes
0
answers
607
views
A rainbow perfect matching in an edge-colored graph with spanning color classes
This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...
- 4,102
10
votes
0
answers
717
views
Has this notion of vertex-coloring of graphs been studied?
In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...
- 155
10
votes
0
answers
302
views
Among regular graphs, do cliques have the highest infection rate?
Consider a graph $G$ with a particular node $i$ labeled as “infected”. Other nodes start uninfected, and will become infected over time according to the following process: To each edge of the graph, ...
- 101
9
votes
5
answers
2k
views
Highly symmetric 6-regular graph with 20 vertices
I'm interested in (node/edge-)symmetric 6-regular graphs on 20 vertices and 60 edges, especially ones with a A5/icosahedral/dodecahedral symmetry group and especially their chromatic number. So far I ...
- 1,746
9
votes
4
answers
546
views
Graph homomorphisms and line graph
If $G,H$ are simple, undirected graphs, we say that they are in a hom(omorphism)-relation if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$.
For any graph $G$ let $L(G)$ denote its ...
- 45.4k
9
votes
3
answers
792
views
Majority coloring for directed graphs
I came up with the following coloring concept when studying neural networks (which are often modelled using directed graphs). No idea whether there is already an established name for it.
If $X$ is a ...
- 45.4k
9
votes
2
answers
559
views
Do planar graphs have an acyclic two-coloring?
A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest.
Does every planar graph have an acyclic two-coloring?
An affirmative ...
- 18.4k
9
votes
2
answers
273
views
Forming Subsets
This question is more of a graph problem. Suppose $A=\{1,2,..,n\}$, and we want to construct the sets $B(i)$,$1\leq i\leq n$, such that $i \not\in B(i)$ and the following constraints on the set $B(i)$ ...
- 91
9
votes
0
answers
312
views
Goldberg-Seymour conjecture
I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ...
- 19.4k
9
votes
0
answers
154
views
Minimal number of colours in distinguishing colouring of biconnected graphs
A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...
- 4,435
8
votes
2
answers
689
views
Induced subgraphs of any given smaller chromatic number
Let $G = (V,E)$ be a simple, undirected graph with $\chi(G)$ infinite. Given a cardinal $\kappa$ with $0 < \kappa < \chi(G)$, is there an induced subgraph $S$ of $G$ with $\chi(S) = \kappa$?
...
- 45.4k
8
votes
3
answers
1k
views
What makes Graph invariants so useful/important?
What makes Graph invariants so useful/important? If I were trying to create a useful graph invariant, what principles should I follow?
My understanding is that they allow one to isolate and study ...
- 121
8
votes
2
answers
722
views
Maximum number of perfect matchings in a planar graph?
What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...
- 13.7k
8
votes
1
answer
214
views
What is known about graphs that permit only one colouring?
Some graphs ($K_n$ or $K_n$ minus any one edge, for instance) only permit one minimal colouring up to different labels of the colours. Is there anything known about these kind of graphs? I can think ...
- 349
8
votes
1
answer
437
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 ...
- 603
8
votes
1
answer
523
views
coincidence between minimal triangulation numbers and chromatic numbers
A friend and I were reading up on the classification of compact surfaces when we realized that the minimal number of triangles in a triangulation of the sphere, torus, and projective plane are 4 (...
- 480
8
votes
1
answer
297
views
How many uniquely colored degree two vertices in 3-coloring of subcubic graph?
Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as ...
- 18.4k
8
votes
3
answers
1k
views
Edge-coloring of the complete graph without any rainbow paths
For a given $2k-1$ edge coloring of the complete graph $K_{2k}$,
say a Hamiltonian path $P$ is a rainbow path if every color appears exactly once in $P$.
My question is
"For each $2k (k \geq 2)$, is ...
- 248
8
votes
1
answer
161
views
Replacing maximum degree with degeneracy in Reed's conjecture
Reed's conjecture says that $\chi(G)\leq \lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$. One can think of $\lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$ as the (rounded-up) average of the trivial lower ...
- 1,666
8
votes
2
answers
377
views
Chromatic number of $C_4$-free graphs
How large can the chromatic number of an $n$-vertex $C_4$-free graph be? If the maximum degree of the graph $G$ is $\Delta$, is there a bound of the form
$\chi(G) \leq O(\Delta/\log(\Delta))$ as in ...
- 428
8
votes
3
answers
248
views
Colorings of triangulations as a generalization of the four-color problem
My question can be viewed as a generalization of the four-color problem. Instead of a planar graph, consider a triangulation of a d-sphere. One wants to color vertices with N colors so that no two ...
- 1,459
8
votes
2
answers
642
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 ...
- 1,924
8
votes
1
answer
374
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
- 3,413
8
votes
1
answer
1k
views
Has anyone seen this graph?
I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone ...
- 2,289
8
votes
0
answers
262
views
Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?
For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...
- 18.4k
8
votes
0
answers
63
views
Color edges of graph w/r/t large induced subgraphs
Can we color the edges of any graph $G$ on $2m-1$ vertices with two colors such that any induced subgraph with at least $m$ edges is non-monochromatic?
If true, this would be sharp as shown by the ...
- 18.4k
8
votes
0
answers
149
views
Edge-colorings of plane graphs: do you know references where the following questions are studied?
Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
- 537
7
votes
1
answer
1k
views
Could the 4-color theorem be proven by contracting snarks?
Suppose someone came up with an algorithm that could take any snark and perform edge contraction to result in the Peterson graph. If an inspection of the algorithm reveals that it works as claimed, ...
- 173
7
votes
1
answer
336
views
Choosing two-colorable subgraph in a triangulation
Consider a planar graph $G$ which is a triangulation.
Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?
It is known that it is not always ...
- 71
7
votes
1
answer
2k
views
Graphs in which any two odd cycles have a common vertex
Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). ...
- 103k