Questions tagged [graph-colorings]
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
623
questions
3
votes
2
answers
224
views
A problem about the connectivity of vertices that must have the same color for any proper minimal coloring of a graph
I've also posted this problem in Math Stack Exchange (here), and it now has an answer in there.
I'm trying to solve a problem about connectivity of entangled vertices in a graph.
Two vertices $u, v$ ...
2
votes
0
answers
973
views
What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + ...$
It is known that $F(x)$ is the generating function of the counting sequence of connected simple graphs with N vertices is given by:
$F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + 853x^7...$
where ...
2
votes
0
answers
136
views
Lower bound for the chromatic number in terms of minimum feedback vertex set
Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$.
We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$
and this bound is sharp.
Is this known or trivial result?
This ...
1
vote
0
answers
57
views
Partitionability and colorability of hypergraphs
Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...
1
vote
0
answers
205
views
Relation between the number of spanning trees and the chromatic number of a graph
The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence:
$$\tau(G)=\tau(G-e)+\tau(G.e),$$
where $e$ is an edge of the graph $G$ and $G-e$ ...
3
votes
4
answers
349
views
Generalization of independence complex of graphs
Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $...
1
vote
1
answer
107
views
Cliques in overlap graphs for words
Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...
10
votes
1
answer
358
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 ...
1
vote
1
answer
69
views
A different version of list coloring
Consider a non-regular bipartite graph $G$ . We consider list edge coloring the edges of the graph by giving lists of cardinality $max(deg(v_i),deg(v_j))+2$ for each edge $e=v_iv_j$ where $deg(v_i)$ ...
2
votes
0
answers
64
views
Analog of Reed's conjecture for hypergraph
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 number, $\Delta$ is the maximum degree, and ...
5
votes
0
answers
166
views
Cardinals realizable by the chromatic number of a regular hypergraph
For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.
If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a ...
1
vote
0
answers
76
views
Total Coloring of a graph with $\Delta\ge\frac{n}{2}$
Consider an even vertex transitive graph $G$, which is not complete, with order $n$ and degree $k$ greater than or equal to half the order. By Hajnal-Szemeredi theorem, we could partition the ...
3
votes
1
answer
111
views
What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?
Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists ...
3
votes
1
answer
294
views
Minimal degree in a critical graph
We say that a finite, simple, undirected graph $G=(V,E)$ is $k$-critical for $k\in\mathbb{N}$ if $\chi(G)=k$ and $\chi(G\setminus \{v\}) = k-1$ for all $v\in V(G)$. Let $\delta(G)$ denote the minimum ...
0
votes
0
answers
60
views
The order of minor in the total graph of a graph
Does the total graph of a regular finite graph with maximum degree $\Delta$ have a $K_{\Delta+2}$ minor?
I think no. It has a clique of order $\Delta+1$. But, I dont think that deleting a few edges ...
0
votes
0
answers
107
views
Minimal degree difference for $k$-critical graphs on $n$ vertices
For a finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of $G$, respectively.
Is there a constant $K\in\mathbb{N}$ with the following ...
-1
votes
1
answer
93
views
Tuza theorem to prove vizing theorem
The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...
3
votes
0
answers
123
views
Lorentzian (=Minkowskian) Hadwiger-Nelson problem: is the chromatic number finite?
Background: Some years ago, I collected a number of thoughts and partial results (which, based on Soifer's Mathematical coloring book, I believed were new) on the Hadwiger-Nelson problem in a note ...
5
votes
1
answer
262
views
Complexity of graph 3 coloring and counting algorithm
3-coloring a graph $G$ is equivalent to partitioning the
vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$
is the order of $G$.
We have $G \...
1
vote
0
answers
121
views
Relation between Betti Numbers and Chromatic Number of a simple graph
Is there a relation between the betti numbers of a graph considered as a simplicial complex and its chromatic number?
Typically the first Betti number is said to be the cyclomatic number of the graph....
12
votes
0
answers
206
views
Does there exist 2-planar graph with chromatic number 8 or 9 or 10
A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
2
votes
1
answer
62
views
A simple equality for book embedding of two graphs
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is ...
3
votes
1
answer
298
views
Concentration of monochromatic edges in a graph
Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
1
vote
0
answers
43
views
Coloration of an interval graph with constraints [closed]
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 ...
3
votes
1
answer
170
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 ...
2
votes
1
answer
103
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
110
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 ...
6
votes
1
answer
574
views
Combinatorial equation system with exponentially many equations in quadratic many variables
A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of ...
5
votes
0
answers
101
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 ...
2
votes
1
answer
524
views
List coloring of tripartite graph [closed]
Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$.
Now, we know that the ...
0
votes
1
answer
91
views
If the core of a graph is a forest, then it is Class 1
It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...
4
votes
0
answers
41
views
Edge orientation of finite triangle-free graphs
Given a finite simple graph without triangles, I am interested in conditions ensuring that there exists an orientation of the edges such that the following holds.
There exists no cycle $x_0,x_1,\dots,...
1
vote
1
answer
92
views
The Total Graph is similar to a line graph
Consider the total graph of a regular graph. From the structure, it seems that it has a similar structure to the line graph ( two different sub-cliques joining at a single point) except that, in ...
0
votes
1
answer
137
views
Chromatic Polynomial when two disjoint graphs are joined at $2$ distinct points [closed]
Consider a graph with chromatic polynomial $P(x)$ joined to a clique of order $k$ in two distinct points (joining here just means interesection of points). Then, what is the chromatic polynomial of ...
0
votes
1
answer
72
views
Edge coloring in dense linear hypergraphs
Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. ...
0
votes
0
answers
77
views
Proving Vizing's and Brooks' theorem using the polynomial approach
It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper ...
1
vote
0
answers
137
views
Linear coefficient of chromatic polynomial
I am interested in the combinatorics of the linear coefficient of the chromatic polynomials. I have the following questions.
What are some class of graphs for which it is possible to calculate this ...
3
votes
1
answer
62
views
Sum-balanceable finite graphs
Let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood
sum function $\mathrm{nsum}_f:V\to\mathbb{Z}$ by setting
$\mathrm{nsum}_f(v) = \sum\{f(w):w\...
1
vote
0
answers
71
views
3-edge colorings for special cubic graphs on a double torus
In Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface it is proven that the task to find these colorings is NP-complete in the general case,...
2
votes
1
answer
289
views
Chromatic number and graph polynomial
If $\prod_{i=1}^t x_i^{e_i}$ is a monomial, define
$$rad\biggl(\prod_{i=1}^t x_i^{e_i}\biggr)$$
to be the number of distinct (nonzero) values of $e_i$.
Now let $G$ be a simple graph with vertices ...
0
votes
0
answers
50
views
A weakened form of list coloring
The list coloring of a simple loopless graph is the assigning of a color from a certain list of colors to every vertex. The list coloring chromatic number of a graph is the minimal cardinality of the ...
-1
votes
1
answer
72
views
Number of maximal independent sets in a simple graph
Consider a simple regular graph on $n$ vertices and size $E$. How many distinct maximal independents can we find at the least in the graph?
I think we can always find at least two maximal ...
4
votes
0
answers
113
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
7
votes
1
answer
99
views
Label distance number and chromatic number of a graph
Let $n\in\mathbb{N}$ be a positive integer, and let $[n] = \{1,\ldots,n\}$. We set $S_n$ for the set of all bijections $\varphi:[n]\to [n]$.
Let $G= ([n], E)$ be a simple, undirected graph, and let $...
2
votes
0
answers
52
views
The graph polynomial of the Total Graph of a Graph
Consider the Total Graph ($T(G)$) of a graph $G$ with vertex set $V$ edge set $E=\{(u,v)\}$ with Line graph $L(G)$ and subdivision graph $S(G)$ (formed by putting a vertex in each edge of the original ...
5
votes
2
answers
195
views
Coloring in Combinatorial Design Generalizing Latin Square
I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $n \times n$ matrix whose entries we want to ...
5
votes
1
answer
310
views
The list chromatic number of some special toroidal grid graphs
A list-assignment $L$ to the vertices of $G$ is the assignment of a list
set $L(v)$ of colours to every vertex $v$ of $G$; and a $k$-list-assignment is a list-assignment such that $|L(v)|\geq k$, for ...
1
vote
0
answers
57
views
A regular independence induced graph in a $\Delta+1$ coloring
Consider any regular graph $G$ with order $n$ and size $E$ and maximum degree $\Delta$. Now, we give a $\Delta+1$ coloring to the vertices such that each vertex and its neighbors receive distinct ...
2
votes
1
answer
291
views
Proving a theorem on coloring a peculiar graph
Consider the graph formed by $k$ cliques of order $k$, any two cliques sharing at most one point in common. Now, by Szekeres-Wilf theorem, I think the graph should be $k$ colorable, as any connected ...
3
votes
2
answers
221
views
Strong chromatic index of some cubic graphs
Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth
Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed.
...