Questions tagged [graph-colorings]

Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.

Filter by
Sorted by
Tagged with
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$ ...
Alma Arjuna's user avatar
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 ...
JaberMac's user avatar
  • 121
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 ...
joro's user avatar
  • 24.2k
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 ...
Dominic van der Zypen's user avatar
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$ ...
vidyarthi's user avatar
  • 2,007
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 $...
Priyavrat Deshpande's user avatar
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'...
frafour's user avatar
  • 435
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 ...
Ethan Splaver's user avatar
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)$ ...
vidyarthi's user avatar
  • 2,007
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 ...
user2679290's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
alex700's user avatar
  • 33
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 ...
Dominic van der Zypen's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Dominic van der Zypen's user avatar
-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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Gro-Tsen's user avatar
  • 29.8k
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 \...
joro's user avatar
  • 24.2k
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....
vidyarthi's user avatar
  • 2,007
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 ...
Xin Zhang's user avatar
  • 1,130
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 ...
Jacob.Z.Lee's user avatar
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 ...
Suman Chakraborty's user avatar
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 ...
user147149's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Mario Krenn's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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,...
Thomas Haettel's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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)$. ...
Dominic van der Zypen's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
GA316's user avatar
  • 1,219
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\...
Dominic van der Zypen's user avatar
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,...
draks ...'s user avatar
  • 457
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
-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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Alex Golovnev's user avatar
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 $...
Dominic van der Zypen's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
John Samples's user avatar
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 ...
Jacob.Z.Lee's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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. ...
EGME's user avatar
  • 1,008

1
3 4
5
6 7
13