On the total and AVD-total coloring of graphs
| Autor: | Bhawani Sankar Panda, Yash Keerti, Shaily Verma |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
lcsh:Mathematics
010102 general mathematics ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION central graphs Total coloring 0102 computer and information sciences total coloring conjecture Computer Science::Computational Geometry lcsh:QA1-939 01 natural sciences Graph Combinatorics total coloring 010201 computation theory & mathematics Discrete Mathematics and Combinatorics 0101 mathematics avd-total coloring chain graphs Computer Science::Information Theory Mathematics ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 3, Pp 820-825 (2020) |
| ISSN: | 2543-3474 0972-8600 |
| Popis: | A total coloring of a graph G is an assignment of colors to the vertices and the edges such that (i) no two adjacent vertices receive same color, (ii) no two adjacent edges receive same color, and (iii) if an edge e is incident on a vertex v, then v and e receive different colors. The least number of colors sufficient for a total coloring of graph G is called its total chromatic number and denoted by An adjacent vertex distinguishing (AVD)-total coloring of G is a total coloring with the additional property that for any adjacent vertices u and v, the set of colors used on the edges incident on u including the color of u is different from the set of colors used on the edges incident on v including the color of v. The adjacent vertex distinguishing (AVD)-total chromatic number of G, is the minimum number of colors required for a valid AVD-total coloring of G. It is conjectured that which is known as total coloring conjecture and is one of the famous open problems. A graph for which the total coloring conjecture holds is called totally colorable graph. The problem of deciding whether or for a totally colorable graph G is called the classification problem for total coloring. However, this classification problem is known to be NP-hard even for bipartite graphs. In this paper, we give a sufficient condition for a bipartite biconvex graph G to have Also, we propose a linear time algorithm to compute the total chromatic number of chain graphs, a proper subclass of biconvex graphs. We prove that the total coloring conjecture holds for the central graph of any graph. Finally, we obtain the AVD-total chromatic number of central graphs for basic graphs such as paths, cycles, stars and complete graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|