Search Results

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its …

Consider an even order, balanced(both partitions have same vertices) bipartite regular graph of order greater than or equal to $12$ and degree atleast six and divisible by $6$. Then is the graph of Ty …

What can we say about the total chromatic number of regular bipartite graphs that are not complete? Can we say they are of type 1[Total Colorable(no adjacent/incident elements have same color) by $\De …

Consider a regular graph of order $n$ and degree $\Delta$. Now, by Brooks' theorem, we can partition the vertices into $\Delta+1$ independent sets. The extreme case of $n$ independent sets is only for …

Consider any graph with $n$ vertices and maximum degree $\Delta$. By Vizing's theorem, the graph could be edge colored(properly) with at most $\Delta+1$ colors. My question pertains as to what the ma …

Consider a symmetric or arc-transitive graph except the odd cycle. Then, is it true that the graph could be partitioned into distinct parts such that each part has equal number of vertices except for …

As an outgrowth of this question, I have another question, that is, why not the definition of conformability includes a $\Delta$ vertex coloring also, instead of only $\Delta+1$ coloring of vertices. …

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 i …

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 co …

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 Lis …

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 …

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 a …

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)$ d …

Suppose, we know that $G$ is a regular graph of odd order that is $k$- edge choosable, where $k$ is the degree. Then, is it true that $\overline{G}$ has list edge chromatic number at most $n-k+1$? I t …

Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded abov …